45 This class was added to support dependencies which do not |
45 This class was added to support dependencies which do not |
46 prevent objects from dying. (i.e. which do not fill up your memory |
46 prevent objects from dying. (i.e. which do not fill up your memory |
47 if you forget to #release it). |
47 if you forget to #release it). |
48 |
48 |
49 [Warning:] |
49 [Warning:] |
50 If you use this, be very careful since the collections size changes |
50 If you use this, be very careful since the collections size changes |
51 'magically' - for example, testing for being nonEmpty and then |
51 'magically' - for example, testing for being nonEmpty and then |
52 removing the first element may fail, since the element may vanish inbetween. |
52 removing the first element may fail, since the element may vanish inbetween. |
53 In general, never trust the value as returned by the size/isEmpty messages. |
53 In general, never trust the value as returned by the size/isEmpty messages. |
54 WeakIdentitySet is not meant as a 'public' class. |
54 WeakIdentitySet is not meant as a 'public' class. |
55 |
55 |
56 [author:] |
56 [author:] |
57 Claus Gittinger |
57 Claus Gittinger |
58 |
58 |
59 [See also:] |
59 [See also:] |
60 WeakArray WeakIdentityDictionary |
60 WeakArray WeakIdentityDictionary |
61 " |
61 " |
62 ! ! |
62 ! ! |
63 |
63 |
64 !WeakIdentitySet class methodsFor:'instance creation'! |
64 !WeakIdentitySet class methodsFor:'instance creation'! |
65 |
65 |
74 !WeakIdentitySet class methodsFor:'queries'! |
74 !WeakIdentitySet class methodsFor:'queries'! |
75 |
75 |
76 goodSizeFrom:arg |
76 goodSizeFrom:arg |
77 "return a good array size for the given argument. |
77 "return a good array size for the given argument. |
78 Since WeakIdentitySets are mostly used for dependency management, we typically |
78 Since WeakIdentitySets are mostly used for dependency management, we typically |
79 have only a small number of elements in the set. |
79 have only a small number of elements in the set. |
80 Therefore use exact size for small sets |
80 Therefore use exact size for small sets |
81 (instead of rounding up to the next prime 11)." |
81 (instead of rounding up to the next prime 11)." |
82 |
82 |
83 arg <= 10 ifTrue:[ |
83 arg <= 10 ifTrue:[ |
84 arg < 1 ifTrue:[^ 1]. |
84 arg < 1 ifTrue:[^ 1]. |
85 ^ arg. |
85 ^ arg. |
86 ]. |
86 ]. |
87 ^ super goodSizeFrom:arg |
87 ^ super goodSizeFrom:arg |
88 ! ! |
88 ! ! |
89 |
89 |
90 !WeakIdentitySet methodsFor:'accessing'! |
90 !WeakIdentitySet methodsFor:'accessing'! |
97 |
97 |
98 |index "{ Class: SmallInteger }" |
98 |index "{ Class: SmallInteger }" |
99 element| |
99 element| |
100 |
100 |
101 index := 1. |
101 index := 1. |
102 "/ allow for the size to change during enumeration |
102 "/ allow for the size to change during enumeration |
103 [index <= keyArray size] whileTrue:[ |
103 [index <= keyArray size] whileTrue:[ |
104 element := keyArray basicAt:index. |
104 element := keyArray basicAt:index. |
105 element notNil ifTrue:[ |
105 element notNil ifTrue:[ |
106 element ~~ 0 ifTrue:[ |
106 element class ~~ SmallInteger ifTrue:[ |
107 element ~~ DeletedEntry ifTrue:[ |
107 element ~~ DeletedEntry ifTrue:[ |
108 element == NilEntry ifTrue:[ |
108 element == NilEntry ifTrue:[ |
109 element := nil. |
109 element := nil. |
110 ]. |
110 ]. |
111 ^ element |
111 ^ element |
112 ] |
112 ] |
113 ] |
113 ] |
114 ]. |
114 ]. |
115 index := index + 1 |
115 index := index + 1 |
116 ]. |
116 ]. |
117 |
117 |
118 ^ exceptionValue value. |
118 ^ exceptionValue value. |
119 ! ! |
119 ! ! |
120 |
120 |
121 !WeakIdentitySet methodsFor:'adding & removing'! |
121 !WeakIdentitySet methodsFor:'adding & removing'! |
122 |
122 |
123 add:newElement |
123 add:newElement |
124 "add the argument, newElement to the receiver. |
124 "add the argument, newElement to the receiver. |
125 Returns the argument, newElement (sigh). |
125 Returns the argument, newElement (sigh). |
126 |
126 |
127 Redefined to avoid synchronization problems, in case of interrupts |
127 Redefined to avoid synchronization problems, in case of interrupts |
128 (otherwise, there could be some other operation on the receiver |
128 (otherwise, there could be some other operation on the receiver |
129 done by another process, which garbles my contents)" |
129 done by another process, which garbles my contents)" |
130 |
130 |
131 |ret| |
131 |ret| |
132 |
132 |
133 (OperatingSystem blockInterrupts) ifTrue:[ |
133 (OperatingSystem blockInterrupts) ifTrue:[ |
134 "/ already blocked |
134 "/ already blocked |
135 ^ super add:newElement. |
135 ^ super add:newElement. |
136 ]. |
136 ]. |
137 |
137 |
138 [ |
138 [ |
139 ret := super add:newElement. |
139 ret := super add:newElement. |
140 ] ensure:[ |
140 ] ensure:[ |
141 OperatingSystem unblockInterrupts |
141 OperatingSystem unblockInterrupts |
142 ]. |
142 ]. |
143 ^ ret |
143 ^ ret |
144 |
144 |
145 "Modified: 29.1.1997 / 15:06:57 / cg" |
145 "Modified: 29.1.1997 / 15:06:57 / cg" |
146 ! |
146 ! |
147 |
147 |
148 remove:anObject ifAbsent:exceptionBlock |
148 remove:anObject ifAbsent:exceptionBlock |
149 "redefined to avoid synchronization problems, in case of interrupts |
149 "redefined to avoid synchronization problems, in case of interrupts |
150 (otherwise, there could be some other operation on the receiver |
150 (otherwise, there could be some other operation on the receiver |
151 done by another process, which garbles my contents)" |
151 done by another process, which garbles my contents)" |
152 |
152 |
153 |ret| |
153 |ret| |
154 |
154 |
155 (OperatingSystem blockInterrupts) ifTrue:[ |
155 (OperatingSystem blockInterrupts) ifTrue:[ |
156 "/ already blocked |
156 "/ already blocked |
157 ^ super remove:anObject ifAbsent:exceptionBlock. |
157 ^ super remove:anObject ifAbsent:exceptionBlock. |
158 ]. |
158 ]. |
159 |
159 |
160 [ |
160 [ |
161 ret := super remove:anObject ifAbsent:exceptionBlock |
161 ret := super remove:anObject ifAbsent:exceptionBlock |
162 ] ensure:[ |
162 ] ensure:[ |
163 OperatingSystem unblockInterrupts |
163 OperatingSystem unblockInterrupts |
164 ]. |
164 ]. |
165 ^ ret |
165 ^ ret |
166 |
166 |
167 "Modified: 29.1.1997 / 15:07:19 / cg" |
167 "Modified: 29.1.1997 / 15:07:19 / cg" |
168 ! ! |
168 ! ! |
173 "an element died - must rehash" |
173 "an element died - must rehash" |
174 |
174 |
175 |wasBlocked| |
175 |wasBlocked| |
176 |
176 |
177 something == #ElementExpired ifTrue:[ |
177 something == #ElementExpired ifTrue:[ |
178 " |
178 " |
179 must block interrupts here - finalization |
179 must block interrupts here - finalization |
180 may be done at low prio in the background |
180 may be done at low prio in the background |
181 finalizer, we do not want to be interrupted |
181 finalizer, we do not want to be interrupted |
182 while rehashing |
182 while rehashing |
183 " |
183 " |
184 wasBlocked := OperatingSystem blockInterrupts. |
184 wasBlocked := OperatingSystem blockInterrupts. |
185 keyArray forAllDeadIndicesDo:[:idx | tally := tally - 1] replacingCorpsesWith:DeletedEntry. |
185 keyArray forAllDeadIndicesDo:[:idx | tally := tally - 1] replacingCorpsesWith:DeletedEntry. |
186 wasBlocked ifFalse:[OperatingSystem unblockInterrupts]. |
186 wasBlocked ifFalse:[OperatingSystem unblockInterrupts]. |
187 ]. |
187 ]. |
188 |
188 |
189 "Created: 7.1.1997 / 17:00:33 / stefan" |
189 "Created: 7.1.1997 / 17:00:33 / stefan" |
190 ! ! |
190 ! ! |
191 |
191 |
200 |
200 |
201 |index "{ Class: SmallInteger }" |
201 |index "{ Class: SmallInteger }" |
202 element| |
202 element| |
203 |
203 |
204 index := 1. |
204 index := 1. |
205 "/ allow for the size to change during enumeration |
205 "/ allow for the size to change during enumeration |
206 [index <= keyArray size] whileTrue:[ |
206 [index <= keyArray size] whileTrue:[ |
207 element := keyArray basicAt:index. |
207 element := keyArray basicAt:index. |
208 element notNil ifTrue:[ |
208 element notNil ifTrue:[ |
209 element ~~ 0 ifTrue:[ |
209 element class ~~ SmallInteger ifTrue:[ |
210 element ~~ DeletedEntry ifTrue:[ |
210 element ~~ DeletedEntry ifTrue:[ |
211 aBlock value:element |
211 aBlock value:element |
212 ] |
212 ] |
213 ] |
213 ] |
214 ]. |
214 ]. |
215 index := index + 1 |
215 index := index + 1 |
216 ] |
216 ] |
217 ! ! |
217 ! ! |
218 |
218 |
219 !WeakIdentitySet methodsFor:'private'! |
219 !WeakIdentitySet methodsFor:'private'! |
220 |
220 |
221 findKeyOrNil:key |
221 findKeyOrNil:key |
222 "Look for the key in the receiver. |
222 "Look for the key in the receiver. |
223 If it is found, return return the index, otherwise |
223 If it is found, return return the index, otherwise |
224 the index of the first unused slot. |
224 the index of the first unused slot. |
225 Grow the receiver, if key was not found, and no unused slots were present. |
225 Grow the receiver, if key was not found, and no unused slots were present. |
226 |
226 |
227 Warning: an empty slot MUST be filled by the sender - it is only to be sent |
227 Warning: an empty slot MUST be filled by the sender - it is only to be sent |
228 by at:put: / add: - like methods." |
228 by at:put: / add: - like methods." |
229 |
229 |
230 |index "{ Class:SmallInteger }" |
230 |index "{ Class:SmallInteger }" |
231 length "{ Class:SmallInteger }" |
231 length "{ Class:SmallInteger }" |
232 startIndex probe |
232 startIndex probe |
233 delIndex "{ Class:SmallInteger }"| |
233 delIndex "{ Class:SmallInteger }"| |
234 |
234 |
235 (OperatingSystem blockInterrupts) ifFalse:[ |
235 (OperatingSystem blockInterrupts) ifFalse:[ |
236 "/ |
236 "/ |
237 "/ may never be entered with interrupts enabled |
237 "/ may never be entered with interrupts enabled |
238 "/ |
238 "/ |
239 OperatingSystem unblockInterrupts. |
239 OperatingSystem unblockInterrupts. |
240 self error:'unblocked call of findKeyOrNil'. |
240 self error:'unblocked call of findKeyOrNil'. |
241 ]. |
241 ]. |
242 |
242 |
243 delIndex := 0. |
243 delIndex := 0. |
244 |
244 |
245 length := keyArray basicSize. |
245 length := keyArray basicSize. |
246 startIndex := index := self initialIndexForKey:key. |
246 startIndex := index := self initialIndexForKey:key. |
247 |
247 |
248 [ |
248 [ |
249 probe := keyArray basicAt:index. |
249 probe := keyArray basicAt:index. |
250 key == probe ifTrue:[^ index]. |
250 key == probe ifTrue:[^ index]. |
251 probe isNil ifTrue:[ |
251 probe isNil ifTrue:[ |
252 delIndex == 0 ifTrue:[^ index]. |
252 delIndex == 0 ifTrue:[^ index]. |
253 keyArray basicAt:delIndex put:nil. |
253 keyArray basicAt:delIndex put:nil. |
254 ^ delIndex |
254 ^ delIndex |
255 ]. |
255 ]. |
256 |
256 |
257 probe == 0 ifTrue:[ |
257 probe class == SmallInteger ifTrue:[ |
258 probe := DeletedEntry. |
258 probe := DeletedEntry. |
259 keyArray basicAt:index put:probe. |
259 keyArray basicAt:index put:probe. |
260 tally := tally - 1. |
260 tally := tally - 1. |
261 ]. |
261 ]. |
262 delIndex == 0 ifTrue:[ |
262 delIndex == 0 ifTrue:[ |
263 probe == DeletedEntry ifTrue:[ |
263 probe == DeletedEntry ifTrue:[ |
264 delIndex := index |
264 delIndex := index |
265 ] |
265 ] |
266 ]. |
266 ]. |
267 |
267 |
268 index == length ifTrue:[ |
268 index == length ifTrue:[ |
269 index := 1 |
269 index := 1 |
270 ] ifFalse:[ |
270 ] ifFalse:[ |
271 index := index + 1 |
271 index := index + 1 |
272 ]. |
272 ]. |
273 index == startIndex ifTrue:[ |
273 index == startIndex ifTrue:[ |
274 delIndex ~~ 0 ifTrue:[ |
274 delIndex ~~ 0 ifTrue:[ |
275 keyArray basicAt:delIndex put:nil. |
275 keyArray basicAt:delIndex put:nil. |
276 ^ delIndex |
276 ^ delIndex |
277 ]. |
277 ]. |
278 ^ self grow findKeyOrNil:key |
278 ^ self grow findKeyOrNil:key |
279 ]. |
279 ]. |
280 ] loop. |
280 ] loop. |
281 |
281 |
282 "Modified: 30.1.1997 / 15:04:38 / cg" |
282 "Modified: 30.1.1997 / 15:04:38 / cg" |
283 ! |
283 ! |
284 |
284 |