Squeak-dev September 2009

squeak-dev@lists.squeakfoundation.org

119 participants
370 discussions

The Trunk: Kernel-ar.253.mcz
by commits＠source.squeak.org 30 Sep '09

30 Sep '09

Andreas Raab uploaded a new version of Kernel to project The Trunk: http://source.squeak.org/trunk/Kernel-ar.253.mcz ==================== Summary ==================== Name: Kernel-ar.253 Author: ar Time: 29 September 2009, 10:19:32 am UUID: 5108df62-e98b-c049-90f5-ca1546d6810d Ancestors: Kernel-ar.252, Kernel-ul.251 Merging Kernel-ul.251: - replaced uses of #findElementOrNil: with #scanFor: - new #scanFor: implementation for MethodDictionary - Added BlockClosue >> #timeToRunWithoutGC which returns the number of milliseconds taken to the block without GC time. =============== Diff against Kernel-ar.252 =============== Item was changed: ----- Method: MethodDictionary>>at:put: (in category 'accessing') ----- at: key put: value "Set the value at key to be value." | index | + index := self scanFor: key. - index := self findElementOrNil: key. (self basicAt: index) == nil ifTrue: [tally := tally + 1. self basicAt: index put: key] ifFalse: [(array at: index) flushCache]. array at: index put: value. self fullCheck. ^ value! Item was changed: ----- Method: MethodDictionary>>removeDangerouslyKey:ifAbsent: (in category 'private') ----- removeDangerouslyKey: key ifAbsent: aBlock "This is not really dangerous. But if normal removal were done WHILE a MethodDict were being used, the system might crash. So instead we make a copy, then do this operation (which is NOT dangerous in a copy that is not being used), and then use the copy after the removal." | index element | + index := self scanFor: key. - index := self findElementOrNil: key. (self basicAt: index) == nil ifTrue: [ ^ aBlock value ]. element := array at: index. array at: index put: nil. self basicAt: index put: nil. tally := tally - 1. self fixCollisionsFrom: index. ^ element! Item was added: + ----- Method: BlockClosure>>timeToRunWithoutGC (in category 'evaluating') ----- + timeToRunWithoutGC + "Answer the number of milliseconds taken to execute this block without GC time." + + ^(SmalltalkImage current vmParameterAt: 8) + + (SmalltalkImage current vmParameterAt: 10) + + self timeToRun - + (SmalltalkImage current vmParameterAt: 8) - + (SmalltalkImage current vmParameterAt: 10) + ! Item was changed: ----- Method: MethodFinder>>initialize2 (in category 'initialize') ----- initialize2 "The methods we are allowed to use. (MethodFinder new initialize) " "Set" #("in class" sizeFor: "testing" "adding" "removing" "enumerating" + "private" array scanFor: - "private" array findElementOrNil: "accessing" someElement) do: [:sel | Approved add: sel]. "Dictionary, IdentityDictionary, IdentitySet" #("accessing" associationAt: associationAt:ifAbsent: at:ifPresent: keyAtIdentityValue: keyAtIdentityValue:ifAbsent: keyAtValue: keyAtValue:ifAbsent: keys "testing" includesKey: ) do: [:sel | Approved add: sel]. #(removeKey: removeKey:ifAbsent: ) do: [:sel | AddAndRemove add: sel]. "LinkedList, Interval, MappedCollection" #("in class" from:to: from:to:by: "accessing" contents) do: [:sel | Approved add: sel]. #( "adding" addFirst: addLast:) do: [:sel | AddAndRemove add: sel]. "OrderedCollection, SortedCollection" #("accessing" after: before: "copying" copyEmpty "adding" growSize "removing" "enumerating" "private" "accessing" sortBlock) do: [:sel | Approved add: sel]. #("adding" add:after: add:afterIndex: add:before: addAllFirst: addAllLast: addFirst: addLast: "removing" removeAt: removeFirst removeLast "accessing" sortBlock:) do: [:sel | AddAndRemove add: sel]. "Character" #("in class, instance creation" allCharacters digitValue: new separators "accessing untypeable characters" backspace cr enter lf linefeed nbsp newPage space tab "constants" alphabet characterTable "accessing" asciiValue digitValue "comparing" "testing" isAlphaNumeric isDigit isLetter isLowercase isSafeForHTTP isSeparator isSpecial isUppercase isVowel tokenish "copying" "converting" asIRCLowercase asLowercase asUppercase ) do: [:sel | Approved add: sel]. "String" #("in class, instance creation" crlf fromPacked: "primitives" findFirstInString:inSet:startingAt: indexOfAscii:inString:startingAt: "internet" valueOfHtmlEntity: "accessing" byteAt: endsWithDigit findAnySubStr:startingAt: findBetweenSubStrs: findDelimiters:startingAt: findString:startingAt: findString:startingAt:caseSensitive: findTokens: findTokens:includes: findTokens:keep: includesSubString: includesSubstring:caseSensitive: indexOf:startingAt: indexOfAnyOf: indexOfAnyOf:ifAbsent: indexOfAnyOf:startingAt: indexOfAnyOf:startingAt:ifAbsent: lineCorrespondingToIndex: lineCount lineNumber: skipAnySubStr:startingAt: skipDelimiters:startingAt: startsWithDigit "comparing" alike: beginsWith: caseSensitiveLessOrEqual: charactersExactlyMatching: compare: crc16 endsWith: endsWithAnyOf: sameAs: startingAt:match:startingAt: "copying" copyReplaceTokens:with: padded:to:with: "converting" asByteArray asDate asDisplayText asFileName asHtml asLegalSelector asPacked asParagraph asText asTime asUnHtml asUrl asUrlRelativeTo: capitalized compressWithTable: contractTo: correctAgainst: encodeForHTTP initialIntegerOrNil keywords quoted sansPeriodSuffix splitInteger stemAndNumericSuffix substrings surroundedBySingleQuotes truncateWithElipsisTo: withBlanksTrimmed withFirstCharacterDownshifted withNoLineLongerThan: withSeparatorsCompacted withoutLeadingDigits withoutTrailingBlanks "displaying" "printing" "system primitives" compare:with:collated: "Celeste" withCRs "internet" decodeMimeHeader decodeQuotedPrintable unescapePercents withInternetLineEndings withSqueakLineEndings withoutQuoting "testing" isAllSeparators lastSpacePosition "paragraph support" indentationIfBlank: "arithmetic" ) do: [:sel | Approved add: sel]. #(byteAt:put: translateToLowercase match:) do: [:sel | AddAndRemove add: sel]. "Symbol" #("in class, private" hasInterned:ifTrue: "access" morePossibleSelectorsFor: possibleSelectorsFor: selectorsContaining: thatStarts:skipping: "accessing" "comparing" "copying" "converting" "printing" "testing" isInfix isKeyword isPvtSelector isUnary) do: [:sel | Approved add: sel]. "Array" #("comparing" "converting" evalStrings "printing" "private" hasLiteralSuchThat:) do: [:sel | Approved add: sel]. "Array2D" #("access" at:at: atCol: atCol:put: atRow: extent extent:fromArray: height width width:height:type:) do: [:sel | Approved add: sel]. #(at:at:add: at:at:put: atRow:put: ) do: [:sel | AddAndRemove add: sel]. "ByteArray" #("accessing" doubleWordAt: wordAt: "platform independent access" longAt:bigEndian: shortAt:bigEndian: unsignedLongAt:bigEndian: unsignedShortAt:bigEndian: "converting") do: [:sel | Approved add: sel]. #(doubleWordAt:put: wordAt:put: longAt:put:bigEndian: shortAt:put:bigEndian: unsignedLongAt:put:bigEndian: unsignedShortAt:put:bigEndian: ) do: [:sel | AddAndRemove add: sel]. "FloatArray" "Dont know what happens when prims not here" false ifTrue: [#("accessing" "arithmetic" *= += -= /= "comparing" "primitives-plugin" primAddArray: primAddScalar: primDivArray: primDivScalar: primMulArray: primMulScalar: primSubArray: primSubScalar: "primitives-translated" primAddArray:withArray:from:to: primMulArray:withArray:from:to: primSubArray:withArray:from:to: "converting" "private" "user interface") do: [:sel | Approved add: sel]. ]. "IntegerArray, WordArray" "RunArray" #("in class, instance creation" runs:values: scanFrom: "accessing" runLengthAt: "adding" "copying" "private" runs values) do: [:sel | Approved add: sel]. #(coalesce addLast:times: repeatLast:ifEmpty: repeatLastIfEmpty: ) do: [:sel | AddAndRemove add: sel]. "Stream -- many operations change its state" #("testing" atEnd) do: [:sel | Approved add: sel]. #("accessing" next: nextMatchAll: nextMatchFor: upToEnd next:put: nextPut: nextPutAll: "printing" print: printHtml: ) do: [:sel | AddAndRemove add: sel]. "PositionableStream" #("accessing" contentsOfEntireFile originalContents peek peekFor: "testing" "positioning" position ) do: [:sel | Approved add: sel]. #(nextDelimited: nextLine upTo: position: reset resetContents setToEnd skip: skipTo: upToAll: ) do: [:sel | AddAndRemove add: sel]. "Because it is so difficult to test the result of an operation on a Stream (you have to supply another Stream in the same state), we don't support Streams beyond the basics. We want to find the messages that convert Streams to other things." "ReadWriteStream" #("file status" closed) do: [:sel | Approved add: sel]. #("accessing" next: on: ) do: [:sel | AddAndRemove add: sel]. "WriteStream" #("in class, instance creation" on:from:to: with: with:from:to: ) do: [:sel | Approved add: sel]. #("positioning" resetToStart "character writing" crtab crtab:) do: [:sel | AddAndRemove add: sel]. "LookupKey, Association, Link" #("accessing" key nextLink) do: [:sel | Approved add: sel]. #(key: key:value: nextLink:) do: [:sel | AddAndRemove add: sel]. "Point" #("in class, instance creation" r:degrees: x:y: "accessing" x y "comparing" "arithmetic" "truncation and round off" "polar coordinates" degrees r theta "point functions" bearingToPoint: crossProduct: dist: dotProduct: eightNeighbors flipBy:centerAt: fourNeighbors grid: nearestPointAlongLineFrom:to: nearestPointOnLineFrom:to: normal normalized octantOf: onLineFrom:to: onLineFrom:to:within: quadrantOf: rotateBy:centerAt: transposed unitVector "converting" asFloatPoint asIntegerPoint corner: extent: rect: "transforming" adhereTo: rotateBy:about: scaleBy: scaleFrom:to: translateBy: "copying" "interpolating" interpolateTo:at:) do: [:sel | Approved add: sel]. "Rectangle" #("in class, instance creation" center:extent: encompassing: left:right:top:bottom: merging: origin:corner: origin:extent: "accessing" area bottom bottomCenter bottomLeft bottomRight boundingBox center corner corners innerCorners left leftCenter origin right rightCenter top topCenter topLeft topRight "comparing" "rectangle functions" adjustTo:along: amountToTranslateWithin: areasOutside: bordersOn:along: encompass: expandBy: extendBy: forPoint:closestSideDistLen: insetBy: insetOriginBy:cornerBy: intersect: merge: pointNearestTo: quickMerge: rectanglesAt:height: sideNearestTo: translatedToBeWithin: withBottom: withHeight: withLeft: withRight: withSide:setTo: withTop: withWidth: "testing" containsPoint: containsRect: hasPositiveExtent intersects: isTall isWide "truncation and round off" "transforming" align:with: centeredBeneath: newRectFrom: squishedWithin: "copying" ) do: [:sel | Approved add: sel]. "Color" #("in class, instance creation" colorFrom: colorFromPixelValue:depth: fromRgbTriplet: gray: h:s:v: r:g:b: r:g:b:alpha: r:g:b:range: "named colors" black blue brown cyan darkGray gray green lightBlue lightBrown lightCyan lightGray lightGreen lightMagenta lightOrange lightRed lightYellow magenta orange red transparent veryDarkGray veryLightGray veryVeryDarkGray veryVeryLightGray white yellow "other" colorNames indexedColors pixelScreenForDepth: quickHighLight: "access" alpha blue brightness green hue luminance red saturation "equality" "queries" isBitmapFill isBlack isGray isSolidFill isTranslucent isTranslucentColor "transformations" alpha: dansDarker darker lighter mixed:with: muchLighter slightlyDarker slightlyLighter veryMuchLighter alphaMixed:with: "groups of shades" darkShades: lightShades: mix:shades: wheel: "printing" shortPrintString "other" colorForInsets rgbTriplet "conversions" asB3DColor asColor balancedPatternForDepth: bitPatternForDepth: closestPixelValue1 closestPixelValue2 closestPixelValue4 closestPixelValue8 dominantColor halfTonePattern1 halfTonePattern2 indexInMap: pixelValueForDepth: pixelWordFor:filledWith: pixelWordForDepth: scaledPixelValue32 "private" privateAlpha privateBlue privateGreen privateRGB privateRed "copying" ) do: [:sel | Approved add: sel]. " For each selector that requires a block argument, add (selector argNum) to the set Blocks." "ourClasses := #(Object Boolean True False UndefinedObject Behavior ClassDescription Class Metaclass MethodContext BlockContext Message Magnitude Date Time Number Integer SmallInteger LargeNegativeInteger LargePositiveInteger Float Fraction Random Collection SequenceableCollection ArrayedCollection Bag Set Dictionary IdentityDictionary IdentitySet LinkedList Interval MappedCollection OrderedCollection SortedCollection Character String Symbol Array Array2D ByteArray FloatArray IntegerArray WordArray RunArray Stream PositionableStream ReadWriteStream WriteStream LookupKey Association Link Point Rectangle Color). ourClasses do: [:clsName | cls := Smalltalk at: clsName. (cls selectors) do: [:aSel | ((Approved includes: aSel) or: [AddAndRemove includes: aSel]) ifTrue: [ (cls formalParametersAt: aSel) withIndexDo: [:tName :ind | (tName endsWith: 'Block') ifTrue: [ Blocks add: (Array with: aSel with: ind)]]]]]. " #((timesRepeat: 1 ) (indexOf:ifAbsent: 2 ) (pairsCollect: 1 ) (mergeSortFrom:to:by: 3 ) (ifNotNil:ifNil: 1 ) (ifNotNil:ifNil: 2 ) (ifNil: 1 ) (at:ifAbsent: 2 ) (ifNil:ifNotNil: 1 ) (ifNil:ifNotNil: 2 ) (ifNotNil: 1 ) (at:modify: 2 ) (identityIndexOf:ifAbsent: 2 ) (sort: 1 ) (sortBlock: 1 ) (detectMax: 1 ) (repeatLastIfEmpty: 1 ) (allSubclassesWithLevelDo:startingLevel: 1 ) (keyAtValue:ifAbsent: 2 ) (in: 1 ) (ifTrue: 1 ) (or: 1 ) (select: 1 ) (inject:into: 2 ) (forPoint:closestSideDistLen: 2 ) (value:ifError: 2 ) (selectorsDo: 1 ) (removeAllSuchThat: 1 ) (keyAtIdentityValue:ifAbsent: 2 ) (detectMin: 1 ) (detect:ifNone: 1 ) (ifTrue:ifFalse: 1 ) (ifTrue:ifFalse: 2 ) (detect:ifNone: 2 ) (hasLiteralSuchThat: 1 ) (indexOfAnyOf:ifAbsent: 2 ) (reject: 1 ) (newRectFrom: 1 ) (removeKey:ifAbsent: 2 ) (at:ifPresent: 2 ) (associationAt:ifAbsent: 2 ) (withIndexCollect: 1 ) (repeatLast:ifEmpty: 2 ) (findLast: 1 ) (indexOf:startingAt:ifAbsent: 3 ) (remove:ifAbsent: 2 ) (ifFalse:ifTrue: 1 ) (ifFalse:ifTrue: 2 ) (caseOf:otherwise: 2 ) (count: 1 ) (collect: 1 ) (sortBy: 1 ) (and: 1 ) (asSortedCollection: 1 ) (with:collect: 2 ) (sourceCodeAt:ifAbsent: 2 ) (detect: 1 ) (collectWithIndex: 1 ) (compiledMethodAt:ifAbsent: 2 ) (bindWithTemp: 1 ) (detectSum: 1 ) (indexOfSubCollection:startingAt:ifAbsent: 3 ) (findFirst: 1 ) (sourceMethodAt:ifAbsent: 2 ) (collect:thenSelect: 1 ) (collect:thenSelect: 2 ) (select:thenCollect: 1 ) (select:thenCollect: 2 ) (ifFalse: 1 ) (indexOfAnyOf:startingAt:ifAbsent: 3 ) (indentationIfBlank: 1 ) ) do: [:anArray | Blocks add: anArray]. self initialize3. " MethodFinder new initialize. MethodFinder new organizationFiltered: TranslucentColor class " "Do not forget class messages for each of these classes" ! Item was changed: ----- Method: MethodDictionary>>at:ifAbsent: (in category 'accessing') ----- at: key ifAbsent: aBlock | index | + index := self scanFor: key. - index := self findElementOrNil: key. (self basicAt: index) == nil ifTrue: [ ^ aBlock value ]. ^ array at: index! Item was changed: ----- Method: MethodDictionary>>at:putNoBecome: (in category 'accessing') ----- at: key putNoBecome: value "Set the value at key to be value. Answer the resulting MethodDictionary" | index | + index := self scanFor: key. - index := self findElementOrNil: key. (self basicAt: index) == nil ifTrue: [tally := tally + 1. self basicAt: index put: key] ifFalse: [(array at: index) flushCache]. array at: index put: value. ^self fullCheckNoBecome! Item was changed: ----- Method: MethodDictionary>>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." - "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 identityHash \\ finish) + 1. - - "Search from (hash mod size) to the end." - start to: finish do: - [:index | ((element := self basicAt: index) == nil or: [element == anObject]) - ifTrue: [^ index ]]. + | index start | + index := start := anObject identityHash \\ array size + 1. + [ + | element | + ((element := self basicAt: index) == nil or: [ element == anObject ]) + ifTrue: [ ^index ]. + (index := index \\ array size + 1) = start ] whileFalse: [ ]. + self errorNoFreeSpace! - "Search from 1 to where we started." - 1 to: start-1 do: - [:index | ((element := self basicAt: index) == nil or: [element == anObject]) - ifTrue: [^ index ]]. - - ^ 0 "No match AND no empty slot"!

1 0

The Trunk: Collections-ar.145.mcz
by commits＠source.squeak.org 30 Sep '09

30 Sep '09

Andreas Raab uploaded a new version of Collections to project The Trunk: http://source.squeak.org/trunk/Collections-ar.145.mcz ==================== Summary ==================== Name: Collections-ar.145 Author: ar Time: 29 September 2009, 10:17:43 am UUID: 4a842b3f-6ec2-c44d-b5d9-082535b2b576 Ancestors: Collections-ar.144 Pseudo-merging Collections-ul.144: - replaced all uses of #findElementOrNil: with #scanFor: - #scanFor: raises an error if it can't find a slot - new #scanFor:, #scanForEmptySlotFor: and #fixCollisionsFrom: implementations - removed unnecessary WeakKeyDictionary >> #scanFor: - added Set >> #errorNoFreeSpace as a common error message for #scanFor: and #scanForEmptySlotFor: =============== Diff against Collections-ar.144 =============== Item was changed: ----- Method: WeakSet>>scanFor: (in category 'private') ----- scanFor: anObject + "Scan the key array for the first slot containing either a nil or a flag (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." - "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 | + | index start | + index := start := anObject hash \\ array size + 1. + [ + | element | + ((element := array at: index) == flag or: [ element = anObject ]) + ifTrue: [ ^index ]. + (index := index \\ array size + 1) = start ] whileFalse: [ ]. + self errorNoFreeSpace! - 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) == flag or: [element = anObject]) - ifTrue: [^ index ]]. - - "Search from 1 to where we started." - 1 to: start-1 do: - [:index | ((element := array at: index) == flag or: [element = anObject]) - ifTrue: [^ index ]]. - - ^ 0 "No match AND no empty slot"! 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 raise an error if no slot is found. This method will be overridden in various subclasses that have different interpretations for matching elements." - "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 := (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 ] ]. + | index start | + index := start := anObject hash \\ array size + 1. + [ + | element | - "Search from 1 to where we started." - 1 to: start - 1 do: [ :index | ((element := array at: index) == nil or: [ element = anObject ]) + ifTrue: [ ^index ]. + (index := index \\ array size + 1) = start ] whileFalse: [ ]. + self errorNoFreeSpace! - ifTrue: [ ^index ] ]. - - ^0 "No match AND no empty slot"! Item was changed: ----- Method: WeakKeyDictionary>>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 element | key isNil ifTrue:[^anObject]. + index := self scanFor: key. - index := self findElementOrNil: key. element := array at: index. element == nil ifTrue: [self atNewIndex: index put: (WeakKeyAssociation key: key value: anObject)] ifFalse: [element value: anObject]. ^ anObject! Item was changed: ----- Method: WeakSet>>add: (in category 'public') ----- add: newObject "Include newObject as one of the receiver's elements, but only if not already present. Answer newObject" | index | newObject ifNil: [self error: 'Sets cannot meaningfully contain nil as an element']. + index := self scanFor: newObject. - index := self findElementOrNil: newObject. ((array at: index) == flag or: [(array at: index) isNil]) ifTrue: [self atNewIndex: index put: newObject]. ^newObject! Item was changed: ----- Method: Set>>add: (in category 'adding') ----- add: newObject "Include newObject as one of the receiver's elements, but only if not already present. Answer newObject." | index | newObject ifNil: [self error: 'Sets cannot meaningfully contain nil as an element']. + index := self scanFor: newObject. - index := self findElementOrNil: newObject. (array at: index) ifNil: [self atNewIndex: index put: newObject]. ^ newObject! Item was changed: ----- 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." + | index start hash | + array size > 4096 + ifTrue: [ hash := anObject identityHash * (array size // 4096) ] - | finish hash start | - (finish := array size) > 4096 - ifTrue: [ hash := anObject identityHash * (finish // 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! - 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 changed: ----- Method: Dictionary>>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." - "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 key = anObject]) - ifTrue: [^ index ]]. + | index start | + index := start := anObject 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! - "Search from 1 to where we started." - 1 to: start-1 do: - [:index | ((element := array at: index) == nil or: [element key = anObject]) - ifTrue: [^ index ]]. - - ^ 0 "No match AND no empty slot"! 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 hash | + array size > 4096 + ifTrue: [ hash := anObject identityHash * (array size // 4096) ] - | finish hash start | - (finish := array size) > 4096 - ifTrue: [ hash := anObject identityHash * (finish // 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! - 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 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." - "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." - | finish hash start element | - 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: [element key == anObject]) - ifTrue: [^ index ]]. - - "Search from 1 to where we started." - 1 to: start-1 do: - [:index | ((element := array at: index) == nil or: [element key == anObject]) - ifTrue: [^ index ]]. + | index start hash | + array size > 4096 + 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! - ^ 0 "No match AND no empty slot"! Item was changed: ----- Method: KeyedSet>>noCheckAdd: (in category 'private') ----- noCheckAdd: anObject + array at: (self scanFor: (keyBlock value: anObject)) put: anObject. - array at: (self findElementOrNil: (keyBlock value: anObject)) put: anObject. tally := tally + 1! Item was changed: ----- Method: Dictionary>>add: (in category 'adding') ----- add: anAssociation | index element | + index := self scanFor: anAssociation key. - index := self findElementOrNil: anAssociation key. element := array at: index. element == nil ifTrue: [self atNewIndex: index put: anAssociation] ifFalse: [element value: anAssociation value]. ^ anAssociation! 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." - "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 hash | - 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: [element key == anObject]) - ifTrue: [^ index ]]. - - "Search from 1 to where we started." - 1 to: start-1 do: - [:index | ((element := array at: index) == nil or: [element key == anObject]) - ifTrue: [^ index ]]. + | index start hash | + array size > 4096 + 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! - ^ 0 "No match AND no empty slot"! Item was changed: ----- 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." + | index start | + index := start := anObject hash \\ array size + 1. + [ + | element | + ((element := array at: index) == flag or: [ element == nil ]) ifTrue: [ ^index ]. + (index := index \\ array size + 1) = start ] whileFalse: [ ]. + self errorNoFreeSpace! - | 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 changed: ----- Method: Dictionary>>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." | index assoc | + index := self scanFor: key. - index := self findElementOrNil: key. assoc := array at: index. nil == assoc ifTrue: [ ^ aBlock value ]. ^ assoc! Item was changed: ----- Method: KeyedSet>>includesKey: (in category 'testing') ----- includesKey: key + ^ (array at: (self scanFor: key)) ~~ nil! - ^ (array at: (self findElementOrNil: key)) ~~ nil! Item was changed: ----- Method: KeyedSet>>remove:ifAbsent: (in category 'removing') ----- remove: oldObject ifAbsent: aBlock | index | + index := self scanFor: (keyBlock value: oldObject). - index := self findElementOrNil: (keyBlock value: oldObject). (array at: index) == nil ifTrue: [ ^ aBlock value ]. array at: index put: nil. tally := tally - 1. self fixCollisionsFrom: index. ^ oldObject! Item was changed: ----- Method: Set>>noCheckAdd: (in category 'private') ----- noCheckAdd: anObject + array at: (self scanFor: anObject) put: anObject. - array at: (self findElementOrNil: anObject) put: anObject. tally := tally + 1! Item was changed: ----- Method: KeyedSet>>removeKey:ifAbsent: (in category 'removing') ----- removeKey: key ifAbsent: aBlock | index obj | + index := self scanFor: key. - index := self findElementOrNil: key. (obj := array at: index) == nil ifTrue: [ ^ aBlock value ]. array at: index put: nil. tally := tally - 1. self fixCollisionsFrom: index. ^ obj! Item was changed: ----- Method: KeyedSet>>includes: (in category 'testing') ----- includes: anObject + ^ (array at: (self scanFor: (keyBlock value: anObject))) ~~ nil! - ^ (array at: (self findElementOrNil: (keyBlock value: anObject))) ~~ nil! 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 hash | + array size > 4096 + ifTrue: [ hash := anObject identityHash * (array size // 4096) ] - | finish hash start | - (finish := array size) > 4096 - ifTrue: [ hash := anObject identityHash * (finish // 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! - 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 changed: ----- Method: Dictionary>>noCheckAdd: (in category 'private') ----- noCheckAdd: anObject + "Must be defined separately for Dictionary because (self scanFor:) expects a key, + not an association. 9/7/96 tk" - "Must be defined separately for Dictionary because (self findElementOrNil:) expects a key, not an association. 9/7/96 tk" + array at: (self scanFor: anObject key) put: anObject. - array at: (self findElementOrNil: anObject key) put: anObject. tally := tally + 1! Item was changed: ----- Method: WeakValueDictionary>>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 element | + index := self scanFor: key. - index := self findElementOrNil: key. element := array at: index. element == nil ifTrue: [self atNewIndex: index put: (WeakValueAssociation key: key value: anObject)] ifFalse: [element value: anObject]. ^ anObject! Item was changed: ----- Method: KeyedSet>>member: (in category 'adding') ----- member: newObject "Include newObject as one of the receiver's elements, if already exists just return it" | index | newObject ifNil: [self error: 'Sets cannot meaningfully contain nil as an element']. + index := self scanFor: (keyBlock value: newObject). - index := self findElementOrNil: (keyBlock value: newObject). (array at: index) ifNotNil: [^ array at: index]. self atNewIndex: index put: newObject. ^ newObject! Item was added: + ----- Method: Set>>errorNoFreeSpace (in category 'private') ----- + errorNoFreeSpace + + self error: 'There is no free space in this collection!!'! 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 raise an error if no slot is found. This method will be overridden in various subclasses that have different interpretations for matching elements." - "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." + | index start | + index := start := (hashBlock + ifNil: [ anObject hash ] + ifNotNil: [ hashBlock value: anObject ]) \\ array size + 1. + [ + | element | + ((element := array at: index) == nil or: [ + equalBlock + ifNil: [ element key = anObject ] + ifNotNil: [ equalBlock value: element key value: anObject ] ]) + ifTrue: [ ^index ]. + (index := index \\ array size + 1) = start ] whileFalse: [ ]. + self errorNoFreeSpace! - | element 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 | ((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 changed: ----- 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." + | index start | + index := start := anObject hash \\ array size + 1. + [ + (array at: index) ifNil: [ ^index ]. + (index := index \\ array size + 1) = start ] whileFalse: [ ]. + self errorNoFreeSpace! - | 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: Set>>like: (in category 'accessing') ----- like: anObject "Answer an object in the receiver that is equal to anObject, nil if no such object is found. Relies heavily on hash properties" | index | + index := self scanFor: anObject. + ^array at: index! - - ^(index := self scanFor: anObject) = 0 - ifFalse: [array at: index]! Item was changed: ----- Method: KeyedSet>>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." | obj | + obj := array at: (self scanFor: key). - obj := array at: (self findElementOrNil: key). obj ifNil: [^ aBlock value]. ^ obj! Item was changed: ----- Method: WeakSet>>do:after: (in category 'public') ----- do: aBlock after: anElement | each startIndex | tally = 0 ifTrue: [^self]. startIndex := anElement ifNil: [1] ifNotNil: + [self scanFor: anElement]. - [self findElementOrNil: anElement]. startIndex + 1 to: array size do: [:index | ((each := array at: index) == nil or: [each == flag]) ifFalse: [aBlock value: each] ]! 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 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 := (hashBlock - "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. + [ + | element | + ((element := array at: index) == nil or: [ + equalBlock + ifNil: [ element = anObject ] + ifNotNil: [ equalBlock value: element value: anObject ] ]) + ifTrue: [ ^index ]. + (index := index \\ array size + 1) = start ] whileFalse: [ ]. + self errorNoFreeSpace! - "Search from (hash mod size) to the end." - start to: array size 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 changed: ----- Method: WeakSet>>remove:ifAbsent: (in category 'public') ----- remove: oldObject ifAbsent: aBlock | index | + index := self scanFor: oldObject. - index := self findElementOrNil: oldObject. (array at: index) == flag ifTrue: [ ^ aBlock value ]. array at: index put: flag. tally := tally - 1. self fixCollisionsFrom: index. ^oldObject! Item was changed: ----- Method: Set>>remove:ifAbsent: (in category 'removing') ----- remove: oldObject ifAbsent: aBlock | index | + index := self scanFor: oldObject. + (array at: index) ifNil: [ ^ aBlock value ]. - index := self findElementOrNil: oldObject. - (array at: index) == nil ifTrue: [ ^ aBlock value ]. array at: index put: nil. tally := tally - 1. self fixCollisionsFrom: index. ^ oldObject! Item was changed: ----- Method: WeakSet>>includes: (in category 'public') ----- includes: anObject + ^(array at: (self scanFor: anObject)) ~~ flag! - ^(array at: (self findElementOrNil: anObject)) ~~ flag! Item was changed: ----- Method: Set>>includes: (in category 'testing') ----- includes: anObject + ^ (array at: (self scanFor: anObject)) ~~ nil! - ^ (array at: (self findElementOrNil: anObject)) ~~ nil! 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 hash | + array size > 4096 + ifTrue: [ hash := anObject identityHash * (array size // 4096) ] - | finish hash start | - (finish := array size) > 4096 - ifTrue: [ hash := anObject identityHash * (finish // 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! - 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 changed: ----- 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." + | index start | + index := start := (hashBlock - | start | - start := (hashBlock ifNil: [ anObject hash ] ifNotNil: [ hashBlock value: anObject ]) \\ array size + 1. + [ + (array at: index) ifNil: [ ^index ]. + (index := index \\ array size + 1) = start ] whileFalse: [ ]. + self errorNoFreeSpace! - "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: WeakSet>>fixCollisionsFrom: (in category 'private') ----- fixCollisionsFrom: start + "The element at start has been removed and replaced by flag. This method moves forward from there, relocating any entries + that had been placed below due to collisions with this one." - that had been placed below due to collisions with this one. - We can be sure that there is an empty slot in this collection - so it's safe to use #scanFor: instead of #findElementOrNil:." + | element index | + index := start. + [ (element := self keyAt: (index := index \\ array size + 1)) == flag ] whileFalse: [ + | newIndex | - | element newIndex | - start + 1 to: array size do: [ :index | - (element := self keyAt: index) == flag ifTrue: [ ^self ]. - (newIndex := self scanFor: element) = index ifFalse: [ - self swap: index with: newIndex ] ]. - 1 to: start do: [ :index | - (element := self keyAt: index) == flag ifTrue: [ ^self ]. (newIndex := self scanFor: element) = index ifFalse: [ self swap: index with: newIndex ] ] ! Item was changed: ----- Method: Set>>fixCollisionsFrom: (in category 'private') ----- 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." - that had been placed below due to collisions with this one. - We can be sure that there is an empty slot in this collection - so it's safe to use #scanFor: instead of #findElementOrNil:." + | element index | + index := start. + [ (element := self keyAt: (index := index \\ array size + 1)) == nil ] whileFalse: [ + | newIndex | - | element newIndex | - start + 1 to: array size do: [ :index | - (element := self keyAt: index) ifNil: [ ^self ]. - (newIndex := self scanFor: element) = index ifFalse: [ - self swap: index with: newIndex ] ]. - 1 to: start do: [ :index | - (element := self keyAt: index) ifNil: [ ^self ]. (newIndex := self scanFor: element) = index ifFalse: [ self swap: index with: newIndex ] ]! Item was changed: ----- Method: IdentitySet>>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." - "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." - | finish hash start element | - 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: [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 ]]. + | index start hash | + array size > 4096 + 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 == anObject ]) + ifTrue: [ ^index ]. + (index := index \\ array size + 1) = start ] whileFalse: [ ]. + self errorNoFreeSpace! - ^ 0 "No match AND no empty slot"! 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." - "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 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 ]]. + | index start hash | + array size > 4096 + 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! - ^ 0 "No match AND no empty slot"! Item was changed: ----- Method: Dictionary>>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) ifNil: [ ^ aBlock value ]. - | index assoc | - index := self findElementOrNil: key. - assoc := array at: index. - assoc == nil ifTrue: [ ^ aBlock value ]. array at: index put: nil. tally := tally - 1. self fixCollisionsFrom: index. + ^association value! - ^ assoc value! Item was changed: ----- Method: KeyedSet>>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." - "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: [(keyBlock value: element) = anObject]) - ifTrue: [^ index ]]. + | index start | + index := start := anObject 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! - "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 changed: ----- Method: Dictionary>>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." | assoc | + assoc := array at: (self scanFor: key). - assoc := array at: (self findElementOrNil: key). assoc ifNil: [^ aBlock value]. ^ assoc value! Item was changed: ----- 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." + | index start | + index := start := (hashBlock - | start | - start := (hashBlock ifNil: [ anObject hash ] ifNotNil: [ hashBlock value: anObject ]) \\ array size + 1. + [ + (array at: index) ifNil: [ ^index ]. + (index := index \\ array size + 1) = start ] whileFalse: [ ]. + self errorNoFreeSpace! - "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: Dictionary>>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 assoc | + index := self scanFor: key. - index := self findElementOrNil: key. assoc := array at: index. assoc ifNil: [self atNewIndex: index put: (Association key: key value: anObject)] ifNotNil: [assoc value: anObject]. ^ anObject! Item was changed: ----- Method: KeyedSet>>add: (in category 'adding') ----- add: newObject "Include newObject as one of the receiver's elements, but only if not already present. Answer newObject." | index | newObject ifNil: [self error: 'Sets cannot meaningfully contain nil as an element']. + index := self scanFor: (keyBlock value: newObject). - index := self findElementOrNil: (keyBlock value: newObject). (array at: index) ifNil: [self atNewIndex: index put: newObject]. ^ newObject! Item was removed: - ----- Method: WeakKeyDictionary>>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 key = anObject]) - ifTrue: [^ index ]]. - - "Search from 1 to where we started." - 1 to: start-1 do: - [:index | ((element := array at: index) == nil or: [element key = anObject]) - ifTrue: [^ index ]]. - - ^ 0 "No match AND no empty slot"!

1 0

The Trunk: Collections-ar.144.mcz
by commits＠source.squeak.org 30 Sep '09

30 Sep '09

Andreas Raab uploaded a new version of Collections to project The Trunk: http://source.squeak.org/trunk/Collections-ar.144.mcz ==================== Summary ==================== Name: Collections-ar.144 Author: ar Time: 29 September 2009, 10:12:54 am UUID: 97570666-a837-924b-a3a6-e1e5ce1e13cf Ancestors: Collections-ar.143, Collections-ul.143 Merging Collections-ul.143: - removed the unused Set >> #withArray: =============== Diff against Collections-ar.143 =============== Item was removed: - ----- Method: Set>>withArray: (in category 'private') ----- - withArray: anArray - "private -- for use only in copy" - array := anArray!

1 0

The Trunk: Kernel-ar.252.mcz
by commits＠source.squeak.org 30 Sep '09

30 Sep '09

Andreas Raab uploaded a new version of Kernel to project The Trunk: http://source.squeak.org/trunk/Kernel-ar.252.mcz ==================== Summary ==================== Name: Kernel-ar.252 Author: ar Time: 29 September 2009, 10:10:31 am UUID: 53948bd4-f611-da40-aebd-2e26a44d43da Ancestors: Kernel-ar.251, Kernel-ul.250 Merging Kernel-ul.250: - removed unnecessary #copy from MethodDictionary =============== Diff against Kernel-ar.251 =============== Item was removed: - ----- Method: MethodDictionary>>copy (in category 'private') ----- - copy - ^ self shallowCopy withArray: array shallowCopy!

1 0

The Trunk: Collections-ar.143.mcz
by commits＠source.squeak.org 30 Sep '09

30 Sep '09

Andreas Raab uploaded a new version of Collections to project The Trunk: http://source.squeak.org/trunk/Collections-ar.143.mcz ==================== Summary ==================== Name: Collections-ar.143 Author: ar Time: 29 September 2009, 10:08:54 am UUID: dbdba380-1e1f-0244-9cd7-1e61d8dcda02 Ancestors: Collections-ar.142, Collections-ul.142 Merging Collections-ul.142: - removed unnecessary #copy from Set and Dictionary =============== Diff against Collections-ar.142 =============== Item was removed: - ----- Method: Set>>copy (in category 'copying') ----- - copy - ^ self shallowCopy withArray: array shallowCopy! Item was removed: - ----- Method: Dictionary>>copy (in category 'private') ----- - copy - "Must copy the associations, or later store will affect both the - original and the copy" - - ^ self shallowCopy withArray: - (array collect: [:assoc | - assoc ifNil: [nil] - ifNotNil: [Association key: assoc key - value: assoc value]])!

1 0

The Trunk: Kernel-ar.251.mcz
by commits＠source.squeak.org 30 Sep '09

30 Sep '09

Andreas Raab uploaded a new version of Kernel to project The Trunk: http://source.squeak.org/trunk/Kernel-ar.251.mcz ==================== Summary ==================== Name: Kernel-ar.251 Author: ar Time: 29 September 2009, 10:06:55 am UUID: 2c77e627-036d-2b46-b6ab-d6b9b6c2fb22 Ancestors: Kernel-nice.250, Kernel-ul.249 Merging Kernel-ul.249: - added MethodDictionary >> #postCopy to replace #copy =============== Diff against Kernel-nice.250 =============== Item was added: + ----- Method: MethodDictionary>>postCopy (in category 'copying') ----- + postCopy + + array := array shallowCopy!

1 0

The Trunk: Collections-ar.142.mcz
by commits＠source.squeak.org 30 Sep '09

30 Sep '09

Andreas Raab uploaded a new version of Collections to project The Trunk: http://source.squeak.org/trunk/Collections-ar.142.mcz ==================== Summary ==================== Name: Collections-ar.142 Author: ar Time: 29 September 2009, 10:04:47 am UUID: 03cd4bc2-d806-7740-a2b3-5a4024943d81 Ancestors: Collections-ar.141, Collections-ul.141 Merging Collections-ul.141: - rewritten Set >> #fixCollisionsFrom: and WeakSet >> #fixCollisionsFrom:, they use #scanFor: instead of #findElementOrNil: - replaced KeyedSet >> #fixCollisionsFrom: with #keyAt: - added #postCopy to Set and subclasses, to replace it's similar but unique mechanism with #copy and #withArray:, these methods have to be removed in another version, but MethodDictionary >> #postCopy has to be added first. - Dictionary >> #values doesn't create an unnecessary copy of the result anymore. =============== Diff against Collections-ar.141 =============== Item was changed: ----- Method: Dictionary>>values (in category 'accessing') ----- values "Answer a Collection containing the receiver's values." + + ^Array new: self size streamContents: [ :stream | + self valuesDo: [ :value | stream nextPut: value] ]! - | out | - out := WriteStream on: (Array new: self size). - self valuesDo: [:value | out nextPut: value]. - ^ out contents! Item was added: + ----- Method: KeyedSet>>keyAt: (in category 'private') ----- + keyAt: index + + ^keyBlock value: (array at: index)! Item was added: + ----- Method: Set>>postCopy (in category 'copying') ----- + postCopy + + array := array shallowCopy! Item was changed: ----- Method: WeakSet>>fixCollisionsFrom: (in category 'private') ----- + fixCollisionsFrom: start + "The element at start has been removed and replaced by flag. - fixCollisionsFrom: index - "The element at index 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. + We can be sure that there is an empty slot in this collection + so it's safe to use #scanFor: instead of #findElementOrNil:." - that had been placed below due to collisions with this one" + | element newIndex | + start + 1 to: array size do: [ :index | + (element := self keyAt: index) == flag ifTrue: [ ^self ]. + (newIndex := self scanFor: element) = index ifFalse: [ + self swap: index with: newIndex ] ]. + 1 to: start do: [ :index | + (element := self keyAt: index) == flag ifTrue: [ ^self ]. + (newIndex := self scanFor: element) = index ifFalse: [ + self swap: index with: newIndex ] ] + ! - | length oldIndex newIndex element | - - oldIndex := index. - length := array size. - [oldIndex = length - ifTrue: [oldIndex := 1] - ifFalse: [oldIndex := oldIndex + 1]. - (element := self keyAt: oldIndex) == flag] - whileFalse: - [newIndex := self findElementOrNil: element. - oldIndex = newIndex ifFalse: [self swap: oldIndex with: newIndex]]! Item was added: + ----- Method: Dictionary>>postCopy (in category 'copying') ----- + postCopy + "Must copy the associations, or later store will affect both the + original and the copy" + + array := array collect: [ :association | + association ifNotNil: [ association copy ] ]! Item was changed: ----- Method: Set>>fixCollisionsFrom: (in category 'private') ----- + fixCollisionsFrom: start + "The element at start has been removed and replaced by nil. - fixCollisionsFrom: index - "The element at index 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. + We can be sure that there is an empty slot in this collection + so it's safe to use #scanFor: instead of #findElementOrNil:." - that had been placed below due to collisions with this one" + | element newIndex | + start + 1 to: array size do: [ :index | + (element := self keyAt: index) ifNil: [ ^self ]. + (newIndex := self scanFor: element) = index ifFalse: [ + self swap: index with: newIndex ] ]. + 1 to: start do: [ :index | + (element := self keyAt: index) ifNil: [ ^self ]. + (newIndex := self scanFor: element) = index ifFalse: [ + self swap: index with: newIndex ] ]! - | length oldIndex newIndex element | - - oldIndex := index. - length := array size. - [oldIndex = length - ifTrue: [oldIndex := 1] - ifFalse: [oldIndex := oldIndex + 1]. - (element := self keyAt: oldIndex) == nil] - whileFalse: - [newIndex := self findElementOrNil: element. - oldIndex = newIndex ifFalse: [self swap: oldIndex with: newIndex]]! Item was removed: - ----- Method: KeyedSet>>fixCollisionsFrom: (in category 'private') ----- - fixCollisionsFrom: index - "The element at index 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" - | length oldIndex newIndex element | - oldIndex := index. - length := array size. - [oldIndex = length - ifTrue: [oldIndex := 1] - ifFalse: [oldIndex := oldIndex + 1]. - (element := self keyAt: oldIndex) == nil] - whileFalse: - [newIndex := self findElementOrNil: (keyBlock value: element). - oldIndex = newIndex ifFalse: [self swap: oldIndex with: newIndex]]!

1 0

The Trunk: Collections-ar.141.mcz
by commits＠source.squeak.org 30 Sep '09

30 Sep '09

Andreas Raab uploaded a new version of Collections to project The Trunk: http://source.squeak.org/trunk/Collections-ar.141.mcz ==================== Summary ==================== Name: Collections-ar.141 Author: ar Time: 29 September 2009, 10:03:18 am UUID: 77f402bd-4b08-bb41-8d16-a0576783e35f Ancestors: Collections-ar.140, Collections-ul.140 Merging Collections-ul.140: - removed unused #scanForNil: implementations (replaced by #scanForEmptySlotFor:), updated comments in #scanFor: =============== Diff against Collections-ar.140 =============== Item was changed: ----- Method: WeakIdentityKeyDictionary>>scanFor: (in category 'private') ----- scanFor: anObject - "ar 10/21/2000: The method has been copied to this location to indicate that whenever #scanFor: changes #scanForNil: must be changed in the receiver as well." "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 hash | 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: [element key == anObject]) ifTrue: [^ index ]]. "Search from 1 to where we started." 1 to: start-1 do: [:index | ((element := array at: index) == nil or: [element key == anObject]) ifTrue: [^ index ]]. ^ 0 "No match AND no empty slot"! Item was changed: ----- Method: WeakKeyDictionary>>scanFor: (in category 'private') ----- scanFor: anObject - "ar 10/21/2000: The method has been copied to this location to indicate that whenever #scanFor: changes #scanForNil: must be changed in the receiver as well." "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 key = anObject]) ifTrue: [^ index ]]. "Search from 1 to where we started." 1 to: start-1 do: [:index | ((element := array at: index) == nil or: [element key = anObject]) ifTrue: [^ index ]]. ^ 0 "No match AND no empty slot"! Item was removed: - ----- Method: WeakIdentityKeyDictionary>>scanForNil: (in category 'private') ----- - scanForNil: anObject - "Private. Scan the key array for the first slot containing nil (indicating an empty slot). Answer the index of that slot." - | start finish hash | - finish := array size. - finish > 4096 - ifTrue: [hash := anObject identityHash * (finish // 4096)] - ifFalse: [hash := anObject identityHash]. - start := (hash \\ array size) + 1. - - "Search from (hash mod size) to the end." - start to: finish do: - [:index | (array at: index) == nil ifTrue: [^ index ]]. - - "Search from 1 to where we started." - 1 to: start-1 do: - [:index | (array at: index) == nil ifTrue: [^ index ]]. - - ^ 0 "No match AND no empty slot"! Item was removed: - ----- Method: WeakKeyDictionary>>scanForNil: (in category 'private') ----- - scanForNil: anObject - "Private. Scan the key array for the first slot containing nil (indicating an empty slot). Answer the index of that slot." - | start finish | - start := (anObject hash \\ array size) + 1. - finish := array size. - - "Search from (hash mod size) to the end." - start to: finish do: - [:index | (array at: index) == nil ifTrue: [^ index ]]. - - "Search from 1 to where we started." - 1 to: start-1 do: - [:index | (array at: index) == nil ifTrue: [^ index ]]. - - ^ 0 "No match AND no empty slot"!

1 0

The Trunk: Collections-ar.140.mcz
by commits＠source.squeak.org 30 Sep '09

30 Sep '09

Andreas Raab uploaded a new version of Collections to project The Trunk: http://source.squeak.org/trunk/Collections-ar.140.mcz ==================== Summary ==================== Name: Collections-ar.140 Author: ar Time: 29 September 2009, 10:01:41 am UUID: 9d84c609-aac0-6043-b47c-c825840b0b83 Ancestors: Collections-ar.139, Collections-ul.139 Merging Collections-ul.139: - remove old implementations of #rehash and #grow from Set's subclasses (except MethodDictionary) =============== Diff against Collections-ar.139 =============== Item was removed: - ----- Method: Dictionary>>rehash (in category 'private') ----- - rehash - "Smalltalk rehash." - | newSelf | - newSelf := self species new: self size. - self associationsDo: [:each | newSelf noCheckAdd: each]. - array := newSelf array! Item was removed: - ----- Method: WeakKeyDictionary>>rehash (in category 'private') ----- - rehash - "Rehash the receiver. Reimplemented to allow for multiple nil keys" - | oldArray assoc newIndex | - oldArray := array. - array := Array new: oldArray size. - tally := 0. - 1 to: array size do:[:i| - assoc := oldArray at: i. - assoc ifNotNil:[ - newIndex := self scanForNil: assoc key. - self atNewIndex: newIndex put: assoc. - ]. - ].! Item was removed: - ----- Method: WeakSet>>grow (in category 'private') ----- - grow - "Grow the elements array and reinsert the old elements" - - self growTo: array size + self growSize! Item was removed: - ----- Method: WeakKeyToCollectionDictionary>>rehash (in category 'as yet unclassified') ----- - rehash - "Rehash the receiver. Reimplemented to remove nils from the collections - that appear as values, and to entirely remove associations with empty collections - as values." - | oldArray assoc cleanedValue newIndex | - oldArray := array. - array := Array new: oldArray size. - tally := 0. - 1 to: array size do: [:i | - assoc := oldArray at: i. - (assoc notNil - and: [(cleanedValue := assoc value copyWithout: nil) notEmpty]) - ifTrue: [newIndex := self scanForNil: assoc key. - assoc value: cleanedValue. - self atNewIndex: newIndex put: assoc]]! Item was removed: - ----- Method: KeyedSet>>rehash (in category 'private') ----- - rehash - | newSelf | - newSelf := self species new: self size. - newSelf keyBlock: keyBlock. - self do: [:each | newSelf noCheckAdd: each]. - array := newSelf array! Item was removed: - ----- Method: WeakSet>>rehash (in category 'private') ----- - rehash - self growTo: array size!

1 0

The Trunk: Collections-ar.139.mcz
by commits＠source.squeak.org 30 Sep '09

30 Sep '09

Andreas Raab uploaded a new version of Collections to project The Trunk: http://source.squeak.org/trunk/Collections-ar.139.mcz ==================== Summary ==================== Name: Collections-ar.139 Author: ar Time: 29 September 2009, 9:57:47 am UUID: bbe161fd-d845-df49-9abf-9c9f13b809f8 Ancestors: Collections-ar.138, Collections-ul.138 Merging Collections-ul.138: - reimplement #rehash, #grow and #finalizeValues: =============== Diff against Collections-ar.138 =============== 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 assoc newIndex | oldArray := array. array := Array new: oldArray size. tally := 0. + 1 to: array size do:[ :i | + | association | + (association := oldArray at: i) ifNotNil: [ + (association key == nil and: [ finiObjects includes: association value ]) + ifFalse:[ + array + at: (self scanForEmptySlotFor: association key) + put: association ] ] ]! - 1 to: array size do:[:i| - assoc := oldArray at: i. - assoc ifNotNil:[ - (assoc key == nil and:[finiObjects includes: assoc value]) ifFalse:[ - newIndex := self scanForNil: assoc key. - self atNewIndex: newIndex put: assoc]. - ]. - ].! Item was changed: ----- Method: Set>>grow (in category 'private') ----- grow "Grow the elements array and reinsert the old elements" + + self growTo: array size + self growSize! - | oldElements | - oldElements := array. - array := Array new: array size + self growSize. - tally := 0. - oldElements do: - [:each | each == nil ifFalse: [self noCheckAdd: each]]! Item was changed: ----- Method: WeakSet>>growTo: (in category 'private') ----- growTo: anInteger "Grow the elements array and reinsert the old elements" | oldElements | oldElements := array. array := WeakArray new: anInteger. array atAllPut: flag. + self noCheckNoGrowFillFrom: oldElements! - tally := 0. - oldElements do: - [:each | (each == flag or: [each == nil]) ifFalse: [self noCheckAdd: each]]! Item was changed: ----- Method: Set>>rehash (in category 'private') ----- rehash + + self growTo: array size! - | newSelf | - newSelf := self species new: self size. - self do: [:each | newSelf noCheckAdd: each]. - array := newSelf array!

1 0

← Newer
1
2
3
4
5
6
7
...
37
Older →

Jump to page: