Lines 27-33
Link Here
|
27 |
* Contributor(s): |
27 |
* Contributor(s): |
28 |
* |
28 |
* |
29 |
* The Original Software is NetBeans. The Initial Developer of the Original |
29 |
* The Original Software is NetBeans. The Initial Developer of the Original |
30 |
* Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun |
30 |
* Software is Sun Microsystems, Inc. Portions Copyright 1997-2007 Sun |
31 |
* Microsystems, Inc. All Rights Reserved. |
31 |
* Microsystems, Inc. All Rights Reserved. |
32 |
* |
32 |
* |
33 |
* If you wish your version of this file to be governed by only the CDDL |
33 |
* If you wish your version of this file to be governed by only the CDDL |
Lines 41-582
Link Here
|
41 |
* Version 2 license, then the option applies only if the new code is |
41 |
* Version 2 license, then the option applies only if the new code is |
42 |
* made subject to such option by the copyright holder. |
42 |
* made subject to such option by the copyright holder. |
43 |
*/ |
43 |
*/ |
|
|
44 |
/* |
45 |
* @(#)WeakSet.java 0.2 07/02/26 |
46 |
*/ |
44 |
|
47 |
|
45 |
package org.openide.util; |
48 |
package org.openide.util; |
46 |
|
49 |
|
47 |
import java.io.IOException; |
50 |
import java.io.IOException; |
48 |
import java.io.ObjectInputStream; |
|
|
49 |
import java.io.ObjectOutputStream; |
50 |
import java.io.Serializable; |
51 |
import java.lang.ref.ReferenceQueue; |
51 |
import java.lang.ref.ReferenceQueue; |
52 |
import java.lang.ref.WeakReference; |
52 |
import java.lang.ref.WeakReference; |
|
|
53 |
import java.util.AbstractCollection; |
54 |
import java.util.AbstractMap; |
53 |
import java.util.AbstractSet; |
55 |
import java.util.AbstractSet; |
54 |
import java.util.ArrayList; |
56 |
import java.util.ArrayList; |
55 |
import java.util.Collection; |
57 |
import java.util.Collection; |
56 |
import java.util.ConcurrentModificationException; |
58 |
import java.util.ConcurrentModificationException; |
57 |
import java.util.Iterator; |
59 |
import java.util.Iterator; |
58 |
import java.util.logging.Level; |
60 |
import java.util.List; |
59 |
import java.util.logging.Logger; |
61 |
import java.util.Map; |
|
|
62 |
import java.util.NoSuchElementException; |
63 |
import java.util.Set; |
60 |
|
64 |
|
61 |
/** Set which holds its members by using of WeakReferences. |
65 |
/** |
62 |
* MT level: unsafe. |
66 |
* This class provides storage functionality with Weak-referenced entries and |
63 |
* <p><strong>Note:</strong> you can instead use |
67 |
* one new method <tt>putIfAbsent<tt> (backed by a hash table) |
64 |
* <pre> |
68 |
* Access to set should be syncronized if used from different threads |
65 |
* Set<T> s = Collections.newSetFromMap(new WeakHashMap<T, Boolean>()); |
69 |
* |
66 |
* </pre> |
70 |
* @see #putIfAbsent(Object) |
67 |
* |
71 |
* @author Vladimir Voskresensky |
68 |
* @author Ales Novak |
72 |
*/ |
69 |
*/ |
73 |
@SuppressWarnings("unchecked") |
70 |
public class WeakSet<E> extends AbstractSet<E> implements Cloneable, Serializable { |
74 |
public class WeakSet <E> extends AbstractSet<E> implements Set<E> { |
71 |
static final long serialVersionUID = 3062376055928236721L; |
75 |
private final SharedKeyWeakHashMap<E, Boolean> m; // The backing map |
|
|
76 |
private transient Set<E> s; // Its keySet |
72 |
|
77 |
|
73 |
/** load factor */ |
78 |
/** |
74 |
private float loadFactor; |
79 |
* Constructs a new, empty <tt>WeakSet</tt> with the given initial |
75 |
|
80 |
* capacity and the given load factor. |
76 |
/** Number of items. */ |
81 |
* |
77 |
private int size; |
82 |
* @param initialCapacity The initial capacity of the <tt>WeakSet</tt> |
78 |
|
83 |
* @param loadFactor The load factor of the <tt>WeakSet</tt> |
79 |
/** Modification count */ |
84 |
* @throws IllegalArgumentException if the initial capacity is negative, |
80 |
private long modcount; |
85 |
* or if the load factor is nonpositive. |
81 |
|
86 |
*/ |
82 |
/** Reference queue of collected weak refs */ |
87 |
public WeakSet(int initialCapacity, float loadFactor) { |
83 |
private transient ReferenceQueue<E> refq; |
88 |
m = new SharedKeyWeakHashMap<E, Boolean>(initialCapacity, loadFactor); |
84 |
|
89 |
s = m.keySet(); |
85 |
/** Count of <tt>null</tt> in this set */ |
|
|
86 |
long nullCount; |
87 |
|
88 |
/** An array of Entries */ |
89 |
private transient Entry<E>[] entries; |
90 |
transient Entry<E> iterChain; |
91 |
|
92 |
/** Constructs a new set. */ |
93 |
public WeakSet() { |
94 |
this(11, 0.75f); |
95 |
} |
90 |
} |
96 |
|
91 |
|
97 |
/** Constructs a new set containing the elements in the specified collection. |
92 |
/** |
98 |
* @param c a collection to add |
93 |
* Constructs a new, empty <tt>WeakSet</tt> with the given initial |
99 |
*/ |
94 |
* capacity and the default load factor (0.75). |
100 |
public WeakSet(Collection<? extends E> c) { |
95 |
* |
101 |
this(); |
96 |
* @param initialCapacity The initial capacity of the <tt>WeakSet</tt> |
102 |
addAll(c); |
97 |
* @throws IllegalArgumentException if the initial capacity is negative |
|
|
98 |
*/ |
99 |
public WeakSet(int initialCapacity) { |
100 |
this(initialCapacity, SharedKeyWeakHashMap.DEFAULT_LOAD_FACTOR); |
103 |
} |
101 |
} |
104 |
|
102 |
|
105 |
/** Constructs a new, empty set; |
103 |
/** |
106 |
* @param initialCapacity initial capacity |
104 |
* Constructs a new, empty <tt>WeakSet</tt> with the default initial |
107 |
*/ |
105 |
* capacity (16) and load factor (0.75). |
108 |
public WeakSet(int initialCapacity) { |
106 |
*/ |
109 |
this(initialCapacity, 0.75f); |
107 |
public WeakSet() { |
|
|
108 |
m = new SharedKeyWeakHashMap<E, Boolean>(); |
109 |
s = m.keySet(); |
110 |
} |
110 |
} |
111 |
|
111 |
|
112 |
/** Constructs a new, empty set; |
112 |
/** |
113 |
* |
113 |
* Constructs a new <tt>WeakSet</tt> with the same mappings as the |
114 |
* @param initialCapacity initial capacity |
114 |
* specified map. The <tt>WeakSet</tt> is created with the default |
115 |
* @param loadFactor load factor |
115 |
* load factor (0.75) and an initial capacity sufficient to hold the |
116 |
*/ |
116 |
* mappings in the specified map. |
117 |
public WeakSet(int initialCapacity, float loadFactor) { |
117 |
* |
118 |
if ((initialCapacity <= 0) || (loadFactor <= 0)) { |
118 |
* @param m the map whose mappings are to be placed in this map |
119 |
throw new IllegalArgumentException(); |
119 |
* @throws NullPointerException if the specified map is null |
|
|
120 |
*/ |
121 |
public WeakSet(Set<? extends E> s) { |
122 |
this(Math.max((int) (s.size() / SharedKeyWeakHashMap.DEFAULT_LOAD_FACTOR) + 1, 16), |
123 |
SharedKeyWeakHashMap.DEFAULT_LOAD_FACTOR); |
124 |
addAll(s); |
125 |
} |
126 |
|
127 |
@Override |
128 |
public void clear() { m.clear(); } |
129 |
public int size() { return m.size(); } |
130 |
@Override |
131 |
public boolean isEmpty() { return m.isEmpty(); } |
132 |
@Override |
133 |
public boolean contains(Object o) { return m.containsKey(o); } |
134 |
@Override |
135 |
public boolean remove(Object o) { return m.remove(o) != null; } |
136 |
public void resize(int newCapacity){ |
137 |
if (size()==0) { |
138 |
m.resize(newCapacity); |
139 |
} |
140 |
} |
141 |
|
142 |
/** |
143 |
* @see #putIfAbsent |
144 |
*/ |
145 |
@Override |
146 |
public boolean add(E e) { return m.put(e, null) == null; } |
147 |
public Iterator<E> iterator() { return s.iterator(); } |
148 |
@Override |
149 |
public Object[] toArray() { return s.toArray(); } |
150 |
@Override |
151 |
public <T> T[] toArray(T[] a) { return s.toArray(a); } |
152 |
@Override |
153 |
public String toString() { return s.toString(); } |
154 |
@Override |
155 |
public int hashCode() { return s.hashCode(); } |
156 |
@Override |
157 |
public boolean equals(Object o) { return o == this || s.equals(o); } |
158 |
@Override |
159 |
public boolean containsAll(Collection<?> c) {return s.containsAll(c);} |
160 |
@Override |
161 |
public boolean removeAll(Collection<?> c) {return s.removeAll(c);} |
162 |
@Override |
163 |
public boolean retainAll(Collection<?> c) {return s.retainAll(c);} |
164 |
// addAll is the only inherited implementation |
165 |
|
166 |
|
167 |
/** |
168 |
* Put object in this set if equal one is not yet in set. |
169 |
* Returns previous set entry if equal object is already in set. |
170 |
* |
171 |
* @param e object to put in set. |
172 |
* @return the previous set entry equals with <tt>e</tt>, or |
173 |
* passed object <tt>e</tt> if there were not entry in set. |
174 |
*/ |
175 |
public E putIfAbsent(E e) { return m.putIfAbsent(e); } |
176 |
|
177 |
private static final long serialVersionUID = 2454657854757543876L; |
178 |
|
179 |
private void readObject(java.io.ObjectInputStream stream) |
180 |
throws IOException, ClassNotFoundException { |
181 |
stream.defaultReadObject(); |
182 |
s = m.keySet(); |
183 |
} |
184 |
|
185 |
// delegate class with only one special method putOrGet |
186 |
// remove entry value field for performance and memory consumption |
187 |
// all other is copied from java.util.WeakHashMap |
188 |
private static class SharedKeyWeakHashMap<K,V> |
189 |
extends AbstractMap<K,V> |
190 |
implements Map<K,V> { |
191 |
|
192 |
/** |
193 |
* The default initial capacity -- MUST be a power of two. |
194 |
*/ |
195 |
private static final int DEFAULT_INITIAL_CAPACITY = 16; |
196 |
|
197 |
/** |
198 |
* The maximum capacity, used if a higher value is implicitly specified |
199 |
* by either of the constructors with arguments. |
200 |
* MUST be a power of two <= 1<<30. |
201 |
*/ |
202 |
private static final int MAXIMUM_CAPACITY = 1 << 30; |
203 |
|
204 |
/** |
205 |
* The load fast used when none specified in constructor. |
206 |
*/ |
207 |
private static final float DEFAULT_LOAD_FACTOR = 0.75f; |
208 |
|
209 |
/** |
210 |
* The table, resized as necessary. Length MUST Always be a power of two. |
211 |
*/ |
212 |
private Entry[] table; |
213 |
|
214 |
/** |
215 |
* The number of key-value mappings contained in this weak hash map. |
216 |
*/ |
217 |
private int size; |
218 |
|
219 |
/** |
220 |
* The next size value at which to resize (capacity * load factor). |
221 |
*/ |
222 |
private int threshold; |
223 |
|
224 |
/** |
225 |
* The load factor for the hash table. |
226 |
*/ |
227 |
private final float loadFactor; |
228 |
|
229 |
/** |
230 |
* Reference queue for cleared WeakEntries |
231 |
*/ |
232 |
private final ReferenceQueue<K> queue = new ReferenceQueue<K>(); |
233 |
|
234 |
/** |
235 |
* The number of times this SharedKeyWeakHashMap has been structurally modified. |
236 |
* Structural modifications are those that change the number of |
237 |
* mappings in the map or otherwise modify its internal structure |
238 |
* (e.g., rehash). This field is used to make iterators on |
239 |
* Collection-views of the map fail-fast. |
240 |
* |
241 |
* @see ConcurrentModificationException |
242 |
*/ |
243 |
private volatile int modCount; |
244 |
|
245 |
/** |
246 |
* Constructs a new, empty <tt>SharedKeyWeakHashMap</tt> with the given initial |
247 |
* capacity and the given load factor. |
248 |
* |
249 |
* @param initialCapacity The initial capacity of the <tt>SharedKeyWeakHashMap</tt> |
250 |
* @param loadFactor The load factor of the <tt>SharedKeyWeakHashMap</tt> |
251 |
* @throws IllegalArgumentException if the initial capacity is negative, |
252 |
* or if the load factor is nonpositive. |
253 |
*/ |
254 |
public SharedKeyWeakHashMap(int initialCapacity, float loadFactor) { |
255 |
if (initialCapacity < 0) |
256 |
throw new IllegalArgumentException("Illegal Initial Capacity: "+ // NOI18N |
257 |
initialCapacity); |
258 |
if (initialCapacity > MAXIMUM_CAPACITY) |
259 |
initialCapacity = MAXIMUM_CAPACITY; |
260 |
|
261 |
if (loadFactor <= 0 || Float.isNaN(loadFactor)) |
262 |
throw new IllegalArgumentException("Illegal Load factor: "+ // NOI18N |
263 |
loadFactor); |
264 |
int capacity = 1; |
265 |
while (capacity < initialCapacity) |
266 |
capacity <<= 1; |
267 |
table = new Entry[capacity]; |
268 |
this.loadFactor = loadFactor; |
269 |
threshold = (int)(capacity * loadFactor); |
120 |
} |
270 |
} |
121 |
|
271 |
|
122 |
size = 0; |
272 |
/** |
123 |
modcount = 0; |
273 |
* Constructs a new, empty <tt>SharedKeyWeakHashMap</tt> with the given initial |
124 |
this.loadFactor = loadFactor; |
274 |
* capacity and the default load factor (0.75). |
125 |
nullCount = 0; |
275 |
* |
126 |
refq = new ReferenceQueue<E>(); |
276 |
* @param initialCapacity The initial capacity of the <tt>SharedKeyWeakHashMap</tt> |
127 |
entries = Entry.createArray(initialCapacity); |
277 |
* @throws IllegalArgumentException if the initial capacity is negative |
128 |
iterChain = null; |
278 |
*/ |
129 |
} |
279 |
public SharedKeyWeakHashMap(int initialCapacity) { |
130 |
|
280 |
this(initialCapacity, DEFAULT_LOAD_FACTOR); |
131 |
/** |
|
|
132 |
* logs iterator chain (for debugging) |
133 |
* @param msg |
134 |
*/ |
135 |
void logIterChain(String msg) { |
136 |
Logger log = Logger.getLogger(WeakSet.class.getName()); |
137 |
log.log(Level.FINE, msg); |
138 |
if (iterChain == null) { |
139 |
log.log(Level.FINE, "Empty"); |
140 |
return; |
141 |
} |
142 |
StringBuilder str = new StringBuilder(); |
143 |
Entry<E> it = iterChain; |
144 |
str.append(size + ": "); |
145 |
while (it != null) { |
146 |
str.append(it.get() + "(" + it.hashcode + ")" + "->"); |
147 |
it = it.iterChainNext; |
148 |
} |
149 |
log.log(Level.FINE, str.toString()); |
150 |
} |
151 |
|
152 |
/** Adds the specified element to this set if it is not already present. |
153 |
* |
154 |
* @param o an Object to add |
155 |
*/ |
156 |
public boolean add(E o) { |
157 |
if (o == null) { |
158 |
size++; |
159 |
nullCount++; |
160 |
modcount++; |
161 |
|
162 |
return true; |
163 |
} |
281 |
} |
164 |
|
282 |
|
165 |
Entry e = object2Entry(o); |
283 |
/** |
|
|
284 |
* Constructs a new, empty <tt>SharedKeyWeakHashMap</tt> with the default initial |
285 |
* capacity (16) and load factor (0.75). |
286 |
*/ |
287 |
public SharedKeyWeakHashMap() { |
288 |
this.loadFactor = DEFAULT_LOAD_FACTOR; |
289 |
threshold = DEFAULT_INITIAL_CAPACITY; |
290 |
table = new Entry[DEFAULT_INITIAL_CAPACITY]; |
291 |
} |
166 |
|
292 |
|
167 |
if (e != null) { |
293 |
/** |
|
|
294 |
* Constructs a new <tt>SharedKeyWeakHashMap</tt> with the same mappings as the |
295 |
* specified map. The <tt>SharedKeyWeakHashMap</tt> is created with the default |
296 |
* load factor (0.75) and an initial capacity sufficient to hold the |
297 |
* mappings in the specified map. |
298 |
* |
299 |
* @param m the map whose mappings are to be placed in this map |
300 |
* @throws NullPointerException if the specified map is null |
301 |
* @since 1.3 |
302 |
*/ |
303 |
public SharedKeyWeakHashMap(Map<? extends K, ? extends V> m) { |
304 |
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, 16), |
305 |
DEFAULT_LOAD_FACTOR); |
306 |
putAll(m); |
307 |
} |
308 |
|
309 |
// internal utilities |
310 |
|
311 |
/** |
312 |
* Value representing null keys inside tables. |
313 |
*/ |
314 |
private static final Object NULL_KEY = new Object(); |
315 |
|
316 |
/** |
317 |
* Use NULL_KEY for key if it is null. |
318 |
*/ |
319 |
private static Object maskNull(Object key) { |
320 |
return (key == null ? NULL_KEY : key); |
321 |
} |
322 |
|
323 |
/** |
324 |
* Returns internal representation of null key back to caller as null. |
325 |
*/ |
326 |
private static <K> K unmaskNull(Object key) { |
327 |
return (K) (key == NULL_KEY ? null : key); |
328 |
} |
329 |
|
330 |
/** |
331 |
* Checks for equality of non-null reference x and possibly-null y. By |
332 |
* default uses Object.equals. |
333 |
*/ |
334 |
static boolean eq(Object x, Object y) { |
335 |
return x == y || x.equals(y); |
336 |
} |
337 |
|
338 |
/** |
339 |
* Returns index for hash code h. |
340 |
*/ |
341 |
static int indexFor(int h, int length) { |
342 |
return h & (length-1); |
343 |
} |
344 |
|
345 |
/** |
346 |
* Expunges stale entries from the table. |
347 |
*/ |
348 |
private void expungeStaleEntries() { |
349 |
Entry<K,V> e; |
350 |
while ( (e = (Entry<K,V>) queue.poll()) != null) { |
351 |
int h = e.hash; |
352 |
int i = indexFor(h, table.length); |
353 |
|
354 |
Entry<K,V> prev = table[i]; |
355 |
Entry<K,V> p = prev; |
356 |
while (p != null) { |
357 |
Entry<K,V> next = p.next; |
358 |
if (p == e) { |
359 |
if (prev == e) |
360 |
table[i] = next; |
361 |
else |
362 |
prev.next = next; |
363 |
e.next = null; // Help GC |
364 |
//e.value = null; // " " |
365 |
size--; |
366 |
break; |
367 |
} |
368 |
prev = p; |
369 |
p = next; |
370 |
} |
371 |
} |
372 |
} |
373 |
|
374 |
/** |
375 |
* Returns the table after first expunging stale entries. |
376 |
*/ |
377 |
private Entry[] getTable() { |
378 |
expungeStaleEntries(); |
379 |
return table; |
380 |
} |
381 |
|
382 |
/** |
383 |
* Returns the number of key-value mappings in this map. |
384 |
* This result is a snapshot, and may not reflect unprocessed |
385 |
* entries that will be removed before next attempted access |
386 |
* because they are no longer referenced. |
387 |
*/ |
388 |
@Override |
389 |
public int size() { |
390 |
if (size == 0) |
391 |
return 0; |
392 |
expungeStaleEntries(); |
393 |
return size; |
394 |
} |
395 |
|
396 |
/** |
397 |
* Returns <tt>true</tt> if this map contains no key-value mappings. |
398 |
* This result is a snapshot, and may not reflect unprocessed |
399 |
* entries that will be removed before next attempted access |
400 |
* because they are no longer referenced. |
401 |
*/ |
402 |
@Override |
403 |
public boolean isEmpty() { |
404 |
return size() == 0; |
405 |
} |
406 |
|
407 |
/** |
408 |
* Returns the value to which the specified key is mapped, |
409 |
* or {@code null} if this map contains no mapping for the key. |
410 |
* |
411 |
* <p>More formally, if this map contains a mapping from a key |
412 |
* {@code k} to a value {@code v} such that {@code (key==null ? k==null : |
413 |
* key.equals(k))}, then this method returns {@code v}; otherwise |
414 |
* it returns {@code null}. (There can be at most one such mapping.) |
415 |
* |
416 |
* <p>A return value of {@code null} does not <i>necessarily</i> |
417 |
* indicate that the map contains no mapping for the key; it's also |
418 |
* possible that the map explicitly maps the key to {@code null}. |
419 |
* The {@link #containsKey containsKey} operation may be used to |
420 |
* distinguish these two cases. |
421 |
* |
422 |
* @see #put(Object, Object) |
423 |
*/ |
424 |
@Override |
425 |
public V get(Object key) { |
426 |
return null; |
427 |
} |
428 |
|
429 |
/** |
430 |
* Returns <tt>true</tt> if this map contains a mapping for the |
431 |
* specified key. |
432 |
* |
433 |
* @param key The key whose presence in this map is to be tested |
434 |
* @return <tt>true</tt> if there is a mapping for <tt>key</tt>; |
435 |
* <tt>false</tt> otherwise |
436 |
*/ |
437 |
@Override |
438 |
public boolean containsKey(Object key) { |
439 |
return getEntry(key) != null; |
440 |
} |
441 |
|
442 |
/** |
443 |
* Returns the entry associated with the specified key in this map. |
444 |
* Returns null if the map contains no mapping for this key. |
445 |
*/ |
446 |
Entry<K,V> getEntry(Object key) { |
447 |
Object k = maskNull(key); |
448 |
int h = hash(k.hashCode()); |
449 |
Entry[] tab = getTable(); |
450 |
int index = indexFor(h, tab.length); |
451 |
Entry<K,V> e = tab[index]; |
452 |
while (e != null && !(e.hash == h && eq(k, e.get()))) |
453 |
e = e.next; |
454 |
return e; |
455 |
} |
456 |
|
457 |
/** |
458 |
* Associates the specified value with the specified key in this map. |
459 |
* If the map previously contained a mapping for this key, the old |
460 |
* value is replaced. |
461 |
* |
462 |
* @param key key with which the specified value is to be associated. |
463 |
* @param value value to be associated with the specified key. |
464 |
* @return the previous value associated with <tt>key</tt>, or |
465 |
* <tt>null</tt> if there was no mapping for <tt>key</tt>. |
466 |
* (A <tt>null</tt> return can also indicate that the map |
467 |
* previously associated <tt>null</tt> with <tt>key</tt>.) |
468 |
*/ |
469 |
@Override |
470 |
public V put(K key, V value) { |
471 |
K k = (K) maskNull(key); |
472 |
int h = hash(k.hashCode()); |
473 |
Entry[] tab = getTable(); |
474 |
int i = indexFor(h, tab.length); |
475 |
|
476 |
for (Entry<K,V> e = tab[i]; e != null; e = e.next) { |
477 |
if (h == e.hash && eq(k, e.get())) { |
478 |
return null; |
479 |
} |
480 |
} |
481 |
|
482 |
modCount++; |
483 |
Entry<K,V> e = tab[i]; |
484 |
tab[i] = new Entry<K,V>(k, queue, h, e); |
485 |
if (++size >= threshold) |
486 |
resize(tab.length * 2); |
487 |
return null; |
488 |
} |
489 |
|
490 |
/** |
491 |
* Rehashes the contents of this map into a new array with a |
492 |
* larger capacity. This method is called automatically when the |
493 |
* number of keys in this map reaches its threshold. |
494 |
* |
495 |
* If current capacity is MAXIMUM_CAPACITY, this method does not |
496 |
* resize the map, but sets threshold to Integer.MAX_VALUE. |
497 |
* This has the effect of preventing future calls. |
498 |
* |
499 |
* @param newCapacity the new capacity, MUST be a power of two; |
500 |
* must be greater than current capacity unless current |
501 |
* capacity is MAXIMUM_CAPACITY (in which case value |
502 |
* is irrelevant). |
503 |
*/ |
504 |
void resize(int newCapacity) { |
505 |
Entry[] oldTable = getTable(); |
506 |
int oldCapacity = oldTable.length; |
507 |
if (oldCapacity == MAXIMUM_CAPACITY) { |
508 |
threshold = Integer.MAX_VALUE; |
509 |
return; |
510 |
} |
511 |
|
512 |
Entry[] newTable = new Entry[newCapacity]; |
513 |
transfer(oldTable, newTable); |
514 |
table = newTable; |
515 |
|
516 |
/* |
517 |
* If ignoring null elements and processing ref queue caused massive |
518 |
* shrinkage, then restore old table. This should be rare, but avoids |
519 |
* unbounded expansion of garbage-filled tables. |
520 |
*/ |
521 |
if (size >= threshold / 2) { |
522 |
threshold = (int)(newCapacity * loadFactor); |
523 |
} else { |
524 |
expungeStaleEntries(); |
525 |
transfer(newTable, oldTable); |
526 |
table = oldTable; |
527 |
} |
528 |
} |
529 |
|
530 |
/** Transfers all entries from src to dest tables */ |
531 |
private void transfer(Entry[] src, Entry[] dest) { |
532 |
for (int j = 0; j < src.length; ++j) { |
533 |
Entry<K,V> e = src[j]; |
534 |
src[j] = null; |
535 |
while (e != null) { |
536 |
Entry<K,V> next = e.next; |
537 |
Object key = e.get(); |
538 |
if (key == null) { |
539 |
e.next = null; // Help GC |
540 |
size--; |
541 |
} else { |
542 |
int i = indexFor(e.hash, dest.length); |
543 |
e.next = dest[i]; |
544 |
dest[i] = e; |
545 |
} |
546 |
e = next; |
547 |
} |
548 |
} |
549 |
} |
550 |
|
551 |
/** |
552 |
* Copies all of the mappings from the specified map to this map. |
553 |
* These mappings will replace any mappings that this map had for any |
554 |
* of the keys currently in the specified map. |
555 |
* |
556 |
* @param m mappings to be stored in this map. |
557 |
* @throws NullPointerException if the specified map is null. |
558 |
*/ |
559 |
@Override |
560 |
public void putAll(Map<? extends K, ? extends V> m) { |
561 |
int numKeysToBeAdded = m.size(); |
562 |
if (numKeysToBeAdded == 0) |
563 |
return; |
564 |
|
565 |
/* |
566 |
* Expand the map if the map if the number of mappings to be added |
567 |
* is greater than or equal to threshold. This is conservative; the |
568 |
* obvious condition is (m.size() + size) >= threshold, but this |
569 |
* condition could result in a map with twice the appropriate capacity, |
570 |
* if the keys to be added overlap with the keys already in this map. |
571 |
* By using the conservative calculation, we subject ourself |
572 |
* to at most one extra resize. |
573 |
*/ |
574 |
if (numKeysToBeAdded > threshold) { |
575 |
int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1); |
576 |
if (targetCapacity > MAXIMUM_CAPACITY) |
577 |
targetCapacity = MAXIMUM_CAPACITY; |
578 |
int newCapacity = table.length; |
579 |
while (newCapacity < targetCapacity) |
580 |
newCapacity <<= 1; |
581 |
if (newCapacity > table.length) |
582 |
resize(newCapacity); |
583 |
} |
584 |
|
585 |
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) |
586 |
put(e.getKey(), null); |
587 |
} |
588 |
|
589 |
/** |
590 |
* Removes the mapping for a key from this weak hash map if it is present. |
591 |
* More formally, if this map contains a mapping from key <tt>k</tt> to |
592 |
* value <tt>v</tt> such that <code>(key==null ? k==null : |
593 |
* key.equals(k))</code>, that mapping is removed. (The map can contain |
594 |
* at most one such mapping.) |
595 |
* |
596 |
* <p>Returns the value to which this map previously associated the key, |
597 |
* or <tt>null</tt> if the map contained no mapping for the key. A |
598 |
* return value of <tt>null</tt> does not <i>necessarily</i> indicate |
599 |
* that the map contained no mapping for the key; it's also possible |
600 |
* that the map explicitly mapped the key to <tt>null</tt>. |
601 |
* |
602 |
* <p>The map will not contain a mapping for the specified key once the |
603 |
* call returns. |
604 |
* |
605 |
* @param key key whose mapping is to be removed from the map |
606 |
* @return the previous value associated with <tt>key</tt>, or |
607 |
* <tt>null</tt> if there was no mapping for <tt>key</tt> |
608 |
*/ |
609 |
@Override |
610 |
public V remove(Object key) { |
611 |
Object k = maskNull(key); |
612 |
int h = hash(k.hashCode()); |
613 |
Entry[] tab = getTable(); |
614 |
int i = indexFor(h, tab.length); |
615 |
Entry<K,V> prev = tab[i]; |
616 |
Entry<K,V> e = prev; |
617 |
|
618 |
while (e != null) { |
619 |
Entry<K,V> next = e.next; |
620 |
if (h == e.hash && eq(k, e.get())) { |
621 |
modCount++; |
622 |
size--; |
623 |
if (prev == e) |
624 |
tab[i] = next; |
625 |
else |
626 |
prev.next = next; |
627 |
return null; |
628 |
} |
629 |
prev = e; |
630 |
e = next; |
631 |
} |
632 |
|
633 |
return null; |
634 |
} |
635 |
|
636 |
|
637 |
|
638 |
/** Special version of remove needed by Entry set */ |
639 |
Entry<K,V> removeMapping(Object o) { |
640 |
if (!(o instanceof Map.Entry)) |
641 |
return null; |
642 |
Entry[] tab = getTable(); |
643 |
Map.Entry entry = (Map.Entry)o; |
644 |
Object k = maskNull(entry.getKey()); |
645 |
int h = hash(k.hashCode()); |
646 |
int i = indexFor(h, tab.length); |
647 |
Entry<K,V> prev = tab[i]; |
648 |
Entry<K,V> e = prev; |
649 |
|
650 |
while (e != null) { |
651 |
Entry<K,V> next = e.next; |
652 |
if (h == e.hash && e.equals(entry)) { |
653 |
modCount++; |
654 |
size--; |
655 |
if (prev == e) |
656 |
tab[i] = next; |
657 |
else |
658 |
prev.next = next; |
659 |
return e; |
660 |
} |
661 |
prev = e; |
662 |
e = next; |
663 |
} |
664 |
|
665 |
return null; |
666 |
} |
667 |
|
668 |
/** |
669 |
* Removes all of the mappings from this map. |
670 |
* The map will be empty after this call returns. |
671 |
*/ |
672 |
@Override |
673 |
public void clear() { |
674 |
// clear out ref queue. We don't need to expunge entries |
675 |
// since table is getting cleared. |
676 |
while (queue.poll() != null) {} |
677 |
|
678 |
modCount++; |
679 |
Entry[] tab = table; |
680 |
for (int i = 0; i < tab.length; ++i) |
681 |
tab[i] = null; |
682 |
size = 0; |
683 |
|
684 |
// Allocation of array may have caused GC, which may have caused |
685 |
// additional entries to go stale. Removing these entries from the |
686 |
// reference queue will make them eligible for reclamation. |
687 |
while (queue.poll() != null) {} |
688 |
} |
689 |
|
690 |
/** |
691 |
* Returns <tt>true</tt> if this map maps one or more keys to the |
692 |
* specified value. |
693 |
* |
694 |
* @param value value whose presence in this map is to be tested |
695 |
* @return <tt>true</tt> if this map maps one or more keys to the |
696 |
* specified value |
697 |
*/ |
698 |
@Override |
699 |
public boolean containsValue(Object value) { |
700 |
if (value==null) |
701 |
return containsNullValue(); |
168 |
return false; |
702 |
return false; |
169 |
} |
703 |
} |
170 |
|
704 |
|
171 |
modcount++; |
705 |
/** |
172 |
size++; |
706 |
* Special-case code for containsValue with null argument |
173 |
|
707 |
*/ |
174 |
int hash = hashIt(o); |
708 |
private boolean containsNullValue() { |
175 |
Entry<E> next = entries[hash]; |
709 |
Entry[] tab = getTable(); |
176 |
iterChain = entries[hash] = new Entry<E>(this, o, refq, next, iterChain); |
710 |
for (int i = tab.length ; i-- > 0 ;) { |
177 |
rehash(); |
711 |
for (Entry e = tab[i] ; e != null ; e = e.next) { |
178 |
|
712 |
return true; |
179 |
return true; |
713 |
} |
180 |
} |
714 |
} |
181 |
|
715 |
return false; |
182 |
/** Removes all of the elements from this set. */ |
|
|
183 |
public void clear() { |
184 |
for (int i = 0; i < entries.length; i++) { |
185 |
entries[i] = null; |
186 |
} |
716 |
} |
187 |
|
717 |
|
188 |
nullCount = 0; |
718 |
/** |
189 |
modcount++; |
719 |
* The entries in this hash table extend WeakReference, using its main ref |
190 |
size = 0; |
720 |
* field as the key. |
191 |
iterChain = null; |
721 |
*/ |
192 |
} |
722 |
private static class Entry<K,V> extends WeakReference<K> implements Map.Entry<K,V> { |
|
|
723 |
private final int hash; |
724 |
private Entry<K,V> next; |
193 |
|
725 |
|
194 |
/** Returns a shallow copy of this WeakSet instance: the elements themselves are not cloned. */ |
726 |
/** |
195 |
public Object clone() { |
727 |
* Creates new entry. |
196 |
WeakSet<E> nws = new WeakSet<E>(1, loadFactor); |
728 |
*/ |
197 |
nws.size = size; |
729 |
Entry(K key, |
198 |
nws.nullCount = nullCount; |
730 |
ReferenceQueue<K> queue, |
199 |
|
731 |
int hash, Entry<K,V> next) { |
200 |
Entry<E>[] cloned = Entry.createArray(entries.length); |
732 |
super(key, queue); |
201 |
nws.entries = cloned; |
733 |
this.hash = hash; |
202 |
|
734 |
this.next = next; |
203 |
for (int i = 0; i < cloned.length; i++) { |
|
|
204 |
Object ref; |
205 |
|
206 |
if ((entries[i] == null) || ((ref = entries[i].get()) == null)) { |
207 |
cloned[i] = null; |
208 |
} else { |
209 |
cloned[i] = ((entries[i] == null) ? null : entries[i].clone(nws.refq)); |
210 |
ref = null; |
211 |
} |
735 |
} |
212 |
|
736 |
|
213 |
// chains into nws iterator chain |
737 |
public K getKey() { |
214 |
Entry<E> entry = cloned[i]; |
738 |
return SharedKeyWeakHashMap.<K>unmaskNull(get()); |
|
|
739 |
} |
215 |
|
740 |
|
216 |
while (entry != null) { |
741 |
public V getValue() { |
217 |
entry.chainIntoIter(nws.iterChain); |
742 |
return null; |
218 |
nws.iterChain = entry; |
743 |
} |
219 |
entry = entry.next; |
744 |
|
|
|
745 |
public V setValue(V newValue) { |
746 |
return null; |
747 |
} |
748 |
|
749 |
@Override |
750 |
public boolean equals(Object o) { |
751 |
if (!(o instanceof Map.Entry)) |
752 |
return false; |
753 |
Map.Entry e = (Map.Entry)o; |
754 |
Object k1 = getKey(); |
755 |
Object k2 = e.getKey(); |
756 |
if (k1 == k2 || (k1 != null && k1.equals(k2))) { |
757 |
return true; |
758 |
} |
759 |
return false; |
760 |
} |
761 |
|
762 |
@Override |
763 |
public int hashCode() { |
764 |
Object k = getKey(); |
765 |
return (k==null ? 0 : k.hashCode()); |
766 |
} |
767 |
|
768 |
@Override |
769 |
public String toString() { |
770 |
return "" + getKey(); // NOI18N |
220 |
} |
771 |
} |
221 |
} |
772 |
} |
222 |
|
773 |
|
223 |
return nws; |
774 |
/** |
224 |
} |
775 |
* Have to copy AbstractMap.SimpleEntry, |
|
|
776 |
* since it appears only in jdk 1.6 |
777 |
*/ |
778 |
private static class SimpleEntry<K,V> |
779 |
implements Map.Entry<K,V>, java.io.Serializable { |
780 |
private static final long serialVersionUID = -8499721149061103585L; |
225 |
|
781 |
|
226 |
/** Returns true if this set contains the specified element. |
782 |
private final K key; |
227 |
* |
783 |
|
228 |
* @param o an Object to examine |
784 |
/** |
229 |
*/ |
785 |
* Creates an entry representing a mapping from the specified |
230 |
public boolean contains(Object o) { |
786 |
* key to the specified value. |
231 |
if (o == null) { |
787 |
* |
232 |
return nullCount > 0; |
788 |
* @param key the key represented by this entry |
|
|
789 |
* @param value the value represented by this entry |
790 |
*/ |
791 |
public SimpleEntry(K key) { |
792 |
this.key = key; |
793 |
} |
794 |
|
795 |
/** |
796 |
* Creates an entry representing the same mapping as the |
797 |
* specified entry. |
798 |
* |
799 |
* @param entry the entry to copy |
800 |
*/ |
801 |
public SimpleEntry(Map.Entry<? extends K, ? extends V> entry) { |
802 |
this.key = entry.getKey(); |
803 |
} |
804 |
|
805 |
/** |
806 |
* Returns the key corresponding to this entry. |
807 |
* |
808 |
* @return the key corresponding to this entry |
809 |
*/ |
810 |
public K getKey() { |
811 |
return key; |
812 |
} |
813 |
|
814 |
/** |
815 |
* Returns the value corresponding to this entry. |
816 |
* |
817 |
* @return the value corresponding to this entry |
818 |
*/ |
819 |
public V getValue() { |
820 |
return null; |
821 |
} |
822 |
|
823 |
/** |
824 |
* Replaces the value corresponding to this entry with the specified |
825 |
* value. |
826 |
* |
827 |
* @param value new value to be stored in this entry |
828 |
* @return the old value corresponding to the entry |
829 |
*/ |
830 |
public V setValue(V value) { |
831 |
return null; |
832 |
} |
833 |
|
834 |
/** |
835 |
* Compares the specified object with this entry for equality. |
836 |
* Returns {@code true} if the given object is also a map entry and |
837 |
* the two entries represent the same mapping. More formally, two |
838 |
* entries {@code e1} and {@code e2} represent the same mapping |
839 |
* if<pre> |
840 |
* (e1.getKey()==null ? |
841 |
* e2.getKey()==null : |
842 |
* e1.getKey().equals(e2.getKey()))</pre> |
843 |
* This ensures that the {@code equals} method works properly across |
844 |
* different implementations of the {@code Map.Entry} interface. |
845 |
* |
846 |
* @param o object to be compared for equality with this map entry |
847 |
* @return {@code true} if the specified object is equal to this map |
848 |
* entry |
849 |
* @see #hashCode |
850 |
*/ |
851 |
@Override |
852 |
public boolean equals(Object o) { |
853 |
if (!(o instanceof Map.Entry)) |
854 |
return false; |
855 |
Map.Entry e = (Map.Entry)o; |
856 |
return eq(key, e.getKey()); |
857 |
} |
858 |
|
859 |
/** |
860 |
* Returns the hash code value for this map entry. The hash code |
861 |
* of a map entry {@code e} is defined to be: <pre> |
862 |
* (e.getKey()==null ? 0 : e.getKey().hashCode())</pre> |
863 |
* This ensures that {@code e1.equals(e2)} implies that |
864 |
* {@code e1.hashCode()==e2.hashCode()} for any two Entries |
865 |
* {@code e1} and {@code e2}, as required by the general |
866 |
* contract of {@link Object#hashCode}. |
867 |
* |
868 |
* @return the hash code value for this map entry |
869 |
* @see #equals |
870 |
*/ |
871 |
@Override |
872 |
public int hashCode() { |
873 |
return (key == null ? 0 : key.hashCode()); |
874 |
} |
875 |
|
876 |
/** |
877 |
* Returns a String representation of this map entry. This |
878 |
* implementation returns the string representation of this |
879 |
* entry's key followed by the equals character ("<tt>=</tt>") |
880 |
* followed by the string representation of this entry's value. |
881 |
* |
882 |
* @return a String representation of this map entry |
883 |
*/ |
884 |
@Override |
885 |
public String toString() { |
886 |
return "" + key; // NOI18N |
887 |
} |
888 |
|
233 |
} |
889 |
} |
234 |
|
890 |
|
235 |
return object2Entry(o) != null; |
891 |
private abstract class HashIterator<T> implements Iterator<T> { |
236 |
} |
892 |
int index; |
|
|
893 |
Entry<K,V> entry = null; |
894 |
Entry<K,V> lastReturned = null; |
895 |
int expectedModCount = modCount; |
237 |
|
896 |
|
238 |
/** Returns true if this set contains no elements. |
897 |
/** |
239 |
*/ |
898 |
* Strong reference needed to avoid disappearance of key |
240 |
public boolean isEmpty() { |
899 |
* between hasNext and next |
241 |
return ((nullCount == 0) && (size() == 0)); |
900 |
*/ |
242 |
} |
901 |
Object nextKey = null; |
243 |
|
902 |
|
244 |
/** Returns an iterator over the elements in this set. */ |
903 |
/** |
245 |
public Iterator<E> iterator() { |
904 |
* Strong reference needed to avoid disappearance of key |
246 |
return new WeakSetIterator(); |
905 |
* between nextEntry() and any use of the entry |
247 |
} |
906 |
*/ |
|
|
907 |
Object currentKey = null; |
248 |
|
908 |
|
249 |
/** Removes the given element from this set if it is present. |
909 |
HashIterator() { |
250 |
* |
910 |
index = (size() != 0 ? table.length : 0); |
251 |
* @param o an Object to remove |
|
|
252 |
* @return <tt>true</tt> if and only if the Object was successfuly removed. |
253 |
*/ |
254 |
public boolean remove(Object o) { |
255 |
if (o == null) { |
256 |
if (nullCount > 0) { |
257 |
nullCount--; |
258 |
modcount++; |
259 |
size--; |
260 |
} |
911 |
} |
261 |
|
912 |
|
262 |
return true; |
913 |
public boolean hasNext() { |
|
|
914 |
Entry[] t = table; |
915 |
|
916 |
while (nextKey == null) { |
917 |
Entry<K,V> e = entry; |
918 |
int i = index; |
919 |
while (e == null && i > 0) |
920 |
e = t[--i]; |
921 |
entry = e; |
922 |
index = i; |
923 |
if (e == null) { |
924 |
currentKey = null; |
925 |
return false; |
926 |
} |
927 |
nextKey = e.get(); // hold on to key in strong ref |
928 |
if (nextKey == null) |
929 |
entry = entry.next; |
930 |
} |
931 |
return true; |
932 |
} |
933 |
|
934 |
/** The common parts of next() across different types of iterators */ |
935 |
protected Entry<K,V> nextEntry() { |
936 |
if (modCount != expectedModCount) |
937 |
throw new ConcurrentModificationException(); |
938 |
if (nextKey == null && !hasNext()) |
939 |
throw new NoSuchElementException(); |
940 |
|
941 |
lastReturned = entry; |
942 |
entry = entry.next; |
943 |
currentKey = nextKey; |
944 |
nextKey = null; |
945 |
return lastReturned; |
946 |
} |
947 |
|
948 |
public void remove() { |
949 |
if (lastReturned == null) |
950 |
throw new IllegalStateException(); |
951 |
if (modCount != expectedModCount) |
952 |
throw new ConcurrentModificationException(); |
953 |
|
954 |
SharedKeyWeakHashMap.this.remove(currentKey); |
955 |
expectedModCount = modCount; |
956 |
lastReturned = null; |
957 |
currentKey = null; |
958 |
} |
959 |
|
263 |
} |
960 |
} |
264 |
|
961 |
|
265 |
Entry e = object2Entry(o); |
962 |
private class ValueIterator extends HashIterator<V> { |
266 |
|
963 |
public V next() { |
267 |
if (e != null) { |
964 |
nextEntry(); |
268 |
modcount++; |
965 |
return null; |
269 |
size--; |
|
|
270 |
e.remove(); |
271 |
rehash(); |
272 |
|
273 |
return true; |
274 |
} |
275 |
|
276 |
return false; |
277 |
} |
278 |
|
279 |
/** @return the number of elements in this set (its cardinality). */ |
280 |
public int size() { |
281 |
checkRefQueue(); |
282 |
|
283 |
return size; |
284 |
} |
285 |
|
286 |
public <T> T[] toArray(T[] array) { |
287 |
ArrayList<E> list = new ArrayList<E>(array.length); |
288 |
Iterator<E> it = iterator(); |
289 |
|
290 |
while (it.hasNext()) { |
291 |
list.add(it.next()); |
292 |
} |
293 |
|
294 |
return list.toArray(array); |
295 |
} |
296 |
|
297 |
public Object[] toArray() { |
298 |
ArrayList<E> list = new ArrayList<E>(); |
299 |
Iterator<E> it = iterator(); |
300 |
|
301 |
while (it.hasNext()) { |
302 |
list.add(it.next()); |
303 |
} |
304 |
|
305 |
return list.toArray(); |
306 |
} |
307 |
|
308 |
// #14772 |
309 |
public String toString() { |
310 |
StringBuffer buf = new StringBuffer(); |
311 |
Iterator e = iterator(); |
312 |
buf.append("["); |
313 |
|
314 |
while (e.hasNext()) { |
315 |
buf.append(String.valueOf(e.next())); |
316 |
|
317 |
if (e.hasNext()) { |
318 |
buf.append(", "); |
319 |
} |
966 |
} |
320 |
} |
967 |
} |
321 |
|
968 |
|
322 |
buf.append("]"); |
969 |
private class KeyIterator extends HashIterator<K> { |
323 |
|
970 |
public K next() { |
324 |
return buf.toString(); |
971 |
return nextEntry().getKey(); |
325 |
} |
|
|
326 |
|
327 |
/** Checks if the queue is empty if not pending weak refs are removed. */ |
328 |
void checkRefQueue() { |
329 |
for (;;) { |
330 |
Entry entry = Entry.class.cast(refq.poll()); |
331 |
|
332 |
if (entry == null) { |
333 |
break; |
334 |
} |
335 |
|
336 |
entry.remove(); |
337 |
size--; |
338 |
} |
339 |
} |
340 |
|
341 |
/** @return modcount */ |
342 |
long modCount() { |
343 |
return modcount; |
344 |
} |
345 |
|
346 |
/** @return an index to entries array */ |
347 |
int hashIt(Object o) { |
348 |
return (o.hashCode() & 0x7fffffff) % entries.length; |
349 |
} |
350 |
|
351 |
/** rehashes this Set */ |
352 |
void rehash() { |
353 |
/* |
354 |
float currentLF = ((float) size) / ((float) entries.length); |
355 |
if (currentLF < loadFactor) { |
356 |
return; |
357 |
} |
358 |
*/ |
359 |
} |
360 |
|
361 |
/** @return an Entry with given object */ |
362 |
private Entry object2Entry(Object o) { |
363 |
checkRefQueue(); // clear ref q |
364 |
|
365 |
int hash = hashIt(o); |
366 |
Entry e = entries[hash]; |
367 |
|
368 |
if (e == null) { |
369 |
return null; |
370 |
} |
371 |
|
372 |
while ((e != null) && !e.equals(o)) { |
373 |
e = e.next; |
374 |
} |
375 |
|
376 |
return e; |
377 |
} |
378 |
|
379 |
private void writeObject(ObjectOutputStream obtos) |
380 |
throws IOException { |
381 |
obtos.defaultWriteObject(); |
382 |
obtos.writeObject(toArray()); |
383 |
} |
384 |
|
385 |
@SuppressWarnings("unchecked") |
386 |
private void readObject(ObjectInputStream obtis) throws IOException, ClassNotFoundException { |
387 |
obtis.defaultReadObject(); |
388 |
|
389 |
Object[] arr = (Object[]) obtis.readObject(); |
390 |
entries = new Entry[(int) (size * 1.5)]; |
391 |
refq = new ReferenceQueue<E>(); |
392 |
|
393 |
for (int i = 0; i < arr.length; i++) { |
394 |
add((E)arr[i]); |
395 |
} |
396 |
} |
397 |
|
398 |
class WeakSetIterator implements Iterator<E> { |
399 |
Entry<E> current; |
400 |
Entry<E> next; |
401 |
E currentObj; |
402 |
E nextObj; |
403 |
final long myModcount; |
404 |
long myNullCount; |
405 |
|
406 |
WeakSetIterator() { |
407 |
myModcount = modCount(); |
408 |
myNullCount = nullCount; |
409 |
current = null; |
410 |
next = null; |
411 |
|
412 |
Entry<E> ee = iterChain; |
413 |
|
414 |
if (ee == null) { |
415 |
return; |
416 |
} |
417 |
|
418 |
E o = ee.get(); |
419 |
|
420 |
while (ee.isEnqueued()) { |
421 |
ee = ee.iterChainNext; |
422 |
|
423 |
if (ee == null) { |
424 |
return; |
425 |
} |
426 |
|
427 |
o = ee.get(); |
428 |
} |
429 |
|
430 |
nextObj = o; |
431 |
next = ee; |
432 |
} |
433 |
|
434 |
public boolean hasNext() { |
435 |
checkModcount(); |
436 |
|
437 |
return ((myNullCount > 0) || (next != null)); |
438 |
} |
439 |
|
440 |
public E next() { |
441 |
checkModcount(); |
442 |
checkRefQueue(); |
443 |
|
444 |
if (myNullCount > 0) { |
445 |
myNullCount--; |
446 |
|
447 |
return null; |
448 |
} else { |
449 |
if (next == null) { |
450 |
throw new java.util.NoSuchElementException(); |
451 |
} |
452 |
|
453 |
current = next; |
454 |
currentObj = nextObj; |
455 |
|
456 |
// move to next requested |
457 |
do { |
458 |
next = next.iterChainNext; |
459 |
|
460 |
if (next == null) { |
461 |
break; |
462 |
} |
463 |
|
464 |
nextObj = next.get(); |
465 |
} while (next.isEnqueued()); |
466 |
|
467 |
return currentObj; |
468 |
} |
972 |
} |
469 |
} |
973 |
} |
470 |
|
974 |
|
471 |
public void remove() { |
975 |
private class EntryIterator extends HashIterator<Map.Entry<K,V>> { |
472 |
checkModcount(); |
976 |
public Map.Entry<K,V> next() { |
473 |
|
977 |
return nextEntry(); |
474 |
if (current == null) { |
|
|
475 |
throw new IllegalStateException(); |
476 |
} |
477 |
|
478 |
current.remove(); |
479 |
size--; |
480 |
} |
481 |
|
482 |
void checkModcount() { |
483 |
if (myModcount != modCount()) { |
484 |
throw new ConcurrentModificationException(); |
485 |
} |
486 |
} |
487 |
} |
488 |
|
489 |
/** Entries of this set */ |
490 |
static class Entry<E> extends WeakReference<E> { |
491 |
/** reference to outer WeakSet */ |
492 |
private WeakSet<E> set; |
493 |
|
494 |
// double linked list |
495 |
Entry<E> prev; |
496 |
Entry<E> next; |
497 |
private final int hashcode; |
498 |
Entry<E> iterChainNext; |
499 |
Entry<E> iterChainPrev; |
500 |
|
501 |
Entry(WeakSet<E> set, E referenced, ReferenceQueue<E> q, Entry<E> next, Entry<E> nextInIter) { |
502 |
super(referenced, q); |
503 |
this.set = set; |
504 |
|
505 |
this.next = next; |
506 |
this.prev = null; |
507 |
|
508 |
if (next != null) { |
509 |
next.prev = this; |
510 |
} |
511 |
|
512 |
if (referenced != null) { |
513 |
hashcode = set.hashIt(referenced); |
514 |
} else { |
515 |
hashcode = 0; |
516 |
} |
517 |
|
518 |
chainIntoIter(nextInIter); |
519 |
} |
520 |
|
521 |
@SuppressWarnings("unchecked") |
522 |
static final <E> Entry<E>[] createArray(int size) { |
523 |
return new Entry[size]; |
524 |
} |
525 |
|
526 |
void chainIntoIter(Entry<E> nextInIter) { |
527 |
iterChainNext = nextInIter; |
528 |
|
529 |
if (nextInIter != null) { |
530 |
nextInIter.iterChainPrev = this; |
531 |
} |
978 |
} |
532 |
} |
979 |
} |
533 |
|
980 |
|
534 |
/** deques itself */ |
981 |
// Views |
535 |
void remove() { |
982 |
|
536 |
if (prev != null) { |
983 |
private transient Set<Map.Entry<K,V>> entrySet = null; |
537 |
prev.next = next; |
984 |
|
|
|
985 |
/** |
986 |
* Returns a {@link Set} view of the keys contained in this map. |
987 |
* The set is backed by the map, so changes to the map are |
988 |
* reflected in the set, and vice-versa. If the map is modified |
989 |
* while an iteration over the set is in progress (except through |
990 |
* the iterator's own <tt>remove</tt> operation), the results of |
991 |
* the iteration are undefined. The set supports element removal, |
992 |
* which removes the corresponding mapping from the map, via the |
993 |
* <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, |
994 |
* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> |
995 |
* operations. It does not support the <tt>add</tt> or <tt>addAll</tt> |
996 |
* operations. |
997 |
*/ |
998 |
@Override |
999 |
public Set<K> keySet() { |
1000 |
Set<K> ks = keySet; |
1001 |
return (ks != null ? ks : (keySet = new KeySet())); |
1002 |
} |
1003 |
|
1004 |
private class KeySet extends AbstractSet<K> { |
1005 |
public Iterator<K> iterator() { |
1006 |
return new KeyIterator(); |
538 |
} |
1007 |
} |
539 |
|
1008 |
|
540 |
if (next != null) { |
1009 |
public int size() { |
541 |
next.prev = prev; |
1010 |
return SharedKeyWeakHashMap.this.size(); |
542 |
} |
1011 |
} |
543 |
|
1012 |
|
544 |
if (iterChainNext != null) { |
1013 |
@Override |
545 |
iterChainNext.iterChainPrev = iterChainPrev; |
1014 |
public boolean contains(Object o) { |
|
|
1015 |
return containsKey(o); |
546 |
} |
1016 |
} |
547 |
|
1017 |
|
548 |
if (iterChainPrev != null) { |
1018 |
@Override |
549 |
iterChainPrev.iterChainNext = iterChainNext; |
1019 |
public boolean remove(Object o) { |
550 |
} else { // root |
1020 |
if (containsKey(o)) { |
551 |
set.iterChain = iterChainNext; |
1021 |
SharedKeyWeakHashMap.this.remove(o); |
|
|
1022 |
return true; |
1023 |
} else |
1024 |
return false; |
552 |
} |
1025 |
} |
553 |
|
1026 |
|
554 |
if (set.entries[hashcode] == this) { |
1027 |
@Override |
555 |
set.entries[hashcode] = next; |
1028 |
public void clear() { |
556 |
} |
1029 |
SharedKeyWeakHashMap.this.clear(); |
557 |
|
|
|
558 |
prev = null; |
559 |
next = null; |
560 |
iterChainNext = null; |
561 |
iterChainPrev = null; |
562 |
} |
563 |
|
564 |
public int hashCode() { |
565 |
return hashcode; |
566 |
} |
567 |
|
568 |
public boolean equals(Object o) { |
569 |
Object oo = get(); |
570 |
|
571 |
if (oo == null) { |
572 |
return false; |
573 |
} else { |
574 |
return oo.equals(o); |
575 |
} |
1030 |
} |
576 |
} |
1031 |
} |
577 |
|
1032 |
|
578 |
public Entry<E> clone(ReferenceQueue<E> q) { |
1033 |
/** |
579 |
return new Entry<E>(set, get(), q, next != null ? next.clone(q) : null, null); |
1034 |
* Returns a {@link Collection} view of the values contained in this map. |
|
|
1035 |
* The collection is backed by the map, so changes to the map are |
1036 |
* reflected in the collection, and vice-versa. If the map is |
1037 |
* modified while an iteration over the collection is in progress |
1038 |
* (except through the iterator's own <tt>remove</tt> operation), |
1039 |
* the results of the iteration are undefined. The collection |
1040 |
* supports element removal, which removes the corresponding |
1041 |
* mapping from the map, via the <tt>Iterator.remove</tt>, |
1042 |
* <tt>Collection.remove</tt>, <tt>removeAll</tt>, |
1043 |
* <tt>retainAll</tt> and <tt>clear</tt> operations. It does not |
1044 |
* support the <tt>add</tt> or <tt>addAll</tt> operations. |
1045 |
*/ |
1046 |
@Override |
1047 |
public Collection<V> values() { |
1048 |
Collection<V> vs = values; |
1049 |
return (vs != null ? vs : (values = new Values())); |
1050 |
} |
1051 |
|
1052 |
private class Values extends AbstractCollection<V> { |
1053 |
public Iterator<V> iterator() { |
1054 |
return new ValueIterator(); |
1055 |
} |
1056 |
|
1057 |
public int size() { |
1058 |
return SharedKeyWeakHashMap.this.size(); |
1059 |
} |
1060 |
|
1061 |
@Override |
1062 |
public boolean contains(Object o) { |
1063 |
return containsValue(o); |
1064 |
} |
1065 |
|
1066 |
@Override |
1067 |
public void clear() { |
1068 |
SharedKeyWeakHashMap.this.clear(); |
1069 |
} |
1070 |
} |
1071 |
|
1072 |
/** |
1073 |
* Returns a {@link Set} view of the mappings contained in this map. |
1074 |
* The set is backed by the map, so changes to the map are |
1075 |
* reflected in the set, and vice-versa. If the map is modified |
1076 |
* while an iteration over the set is in progress (except through |
1077 |
* the iterator's own <tt>remove</tt> operation, or through the |
1078 |
* <tt>setValue</tt> operation on a map entry returned by the |
1079 |
* iterator) the results of the iteration are undefined. The set |
1080 |
* supports element removal, which removes the corresponding |
1081 |
* mapping from the map, via the <tt>Iterator.remove</tt>, |
1082 |
* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and |
1083 |
* <tt>clear</tt> operations. It does not support the |
1084 |
* <tt>add</tt> or <tt>addAll</tt> operations. |
1085 |
*/ |
1086 |
public Set<Map.Entry<K,V>> entrySet() { |
1087 |
Set<Map.Entry<K,V>> es = entrySet; |
1088 |
return es != null ? es : (entrySet = new EntrySet()); |
1089 |
} |
1090 |
|
1091 |
private class EntrySet extends AbstractSet<Map.Entry<K,V>> { |
1092 |
public Iterator<Map.Entry<K,V>> iterator() { |
1093 |
return new EntryIterator(); |
1094 |
} |
1095 |
|
1096 |
@Override |
1097 |
public boolean contains(Object o) { |
1098 |
if (!(o instanceof Map.Entry)) |
1099 |
return false; |
1100 |
Map.Entry e = (Map.Entry)o; |
1101 |
Entry candidate = getEntry(e.getKey()); |
1102 |
return candidate != null && candidate.equals(e); |
1103 |
} |
1104 |
|
1105 |
@Override |
1106 |
public boolean remove(Object o) { |
1107 |
return removeMapping(o) != null; |
1108 |
} |
1109 |
|
1110 |
public int size() { |
1111 |
return SharedKeyWeakHashMap.this.size(); |
1112 |
} |
1113 |
|
1114 |
@Override |
1115 |
public void clear() { |
1116 |
SharedKeyWeakHashMap.this.clear(); |
1117 |
} |
1118 |
|
1119 |
private List<Map.Entry<K,V>> deepCopy() { |
1120 |
List<Map.Entry<K,V>> list = new ArrayList<Map.Entry<K,V>>(size()); |
1121 |
for (Map.Entry<K,V> e : this) |
1122 |
// have to use own class since AbstractMap.SimpleEntry is appears only in jdk 1.6 |
1123 |
list.add(new /*AbstractMap.*/SimpleEntry<K,V>(e)); |
1124 |
return list; |
1125 |
} |
1126 |
|
1127 |
@Override |
1128 |
public Object[] toArray() { |
1129 |
return deepCopy().toArray(); |
1130 |
} |
1131 |
|
1132 |
@Override |
1133 |
public <T> T[] toArray(T[] a) { |
1134 |
return deepCopy().toArray(a); |
1135 |
} |
1136 |
} |
1137 |
|
1138 |
//////////////////////////////////////////////////////////////////////////// |
1139 |
// new changes |
1140 |
|
1141 |
/** |
1142 |
* Applies a supplemental hash function to a given hashCode, which |
1143 |
* defends against poor quality hash functions. This is critical |
1144 |
* because HashMap uses power-of-two length hash tables, that |
1145 |
* otherwise encounter collisions for hashCodes that do not differ |
1146 |
* in lower bits. Note: Null keys always map to hash 0, thus index 0. |
1147 |
*/ |
1148 |
static int hash(int h) { |
1149 |
// This function ensures that hashCodes that differ only by |
1150 |
// constant multiples at each bit position have a bounded |
1151 |
// number of collisions (approximately 8 at default load factor). |
1152 |
h ^= (h >>> 20) ^ (h >>> 12); |
1153 |
return h ^ (h >>> 7) ^ (h >>> 4); |
1154 |
} |
1155 |
|
1156 |
// Views |
1157 |
|
1158 |
/** |
1159 |
* Each of these fields are initialized to contain an instance of the |
1160 |
* appropriate view the first time this view is requested. The views are |
1161 |
* stateless, so there's no reason to create more than one of each. |
1162 |
*/ |
1163 |
transient volatile Set<K> keySet = null; |
1164 |
transient volatile Collection<V> values = null; |
1165 |
|
1166 |
/** |
1167 |
* Put specified key in this set if key is not yet in set. |
1168 |
* returns previous value in set if key already in set. |
1169 |
* |
1170 |
* @param key key to put in set. |
1171 |
* @return the previous set entry equals with <tt>key</tt>, or |
1172 |
* new <tt>key</tt> if there were not entry in set. |
1173 |
*/ |
1174 |
private K putIfAbsent(K key) { |
1175 |
K k = (K) maskNull(key); |
1176 |
int h = hash(k.hashCode()); |
1177 |
Entry[] tab = getTable(); |
1178 |
int i = indexFor(h, tab.length); |
1179 |
|
1180 |
Entry<K,V> e = tab[i]; |
1181 |
while (e != null) { |
1182 |
if (e.hash == h) { |
1183 |
K refedKey = e.get(); |
1184 |
if (eq(k, refedKey)) { |
1185 |
return refedKey; |
1186 |
} |
1187 |
} |
1188 |
e = e.next; |
1189 |
} |
1190 |
|
1191 |
modCount++; |
1192 |
e = tab[i]; |
1193 |
tab[i] = new Entry<K,V>(k, queue, h, e); |
1194 |
if (++size >= threshold) |
1195 |
resize(tab.length * 2); |
1196 |
return k; |
580 |
} |
1197 |
} |
581 |
} |
1198 |
} |
582 |
} |
1199 |
} |