jaroslav@1258
|
1 |
/*
|
jaroslav@1258
|
2 |
* Copyright (c) 1998, 2010, Oracle and/or its affiliates. All rights reserved.
|
jaroslav@1258
|
3 |
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
|
jaroslav@1258
|
4 |
*
|
jaroslav@1258
|
5 |
* This code is free software; you can redistribute it and/or modify it
|
jaroslav@1258
|
6 |
* under the terms of the GNU General Public License version 2 only, as
|
jaroslav@1258
|
7 |
* published by the Free Software Foundation. Oracle designates this
|
jaroslav@1258
|
8 |
* particular file as subject to the "Classpath" exception as provided
|
jaroslav@1258
|
9 |
* by Oracle in the LICENSE file that accompanied this code.
|
jaroslav@1258
|
10 |
*
|
jaroslav@1258
|
11 |
* This code is distributed in the hope that it will be useful, but WITHOUT
|
jaroslav@1258
|
12 |
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
jaroslav@1258
|
13 |
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
jaroslav@1258
|
14 |
* version 2 for more details (a copy is included in the LICENSE file that
|
jaroslav@1258
|
15 |
* accompanied this code).
|
jaroslav@1258
|
16 |
*
|
jaroslav@1258
|
17 |
* You should have received a copy of the GNU General Public License version
|
jaroslav@1258
|
18 |
* 2 along with this work; if not, write to the Free Software Foundation,
|
jaroslav@1258
|
19 |
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
|
jaroslav@1258
|
20 |
*
|
jaroslav@1258
|
21 |
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
|
jaroslav@1258
|
22 |
* or visit www.oracle.com if you need additional information or have any
|
jaroslav@1258
|
23 |
* questions.
|
jaroslav@1258
|
24 |
*/
|
jaroslav@1258
|
25 |
|
jaroslav@1258
|
26 |
package java.util;
|
jaroslav@1258
|
27 |
import java.lang.ref.WeakReference;
|
jaroslav@1258
|
28 |
import java.lang.ref.ReferenceQueue;
|
jaroslav@1258
|
29 |
|
jaroslav@1258
|
30 |
|
jaroslav@1258
|
31 |
/**
|
jaroslav@1258
|
32 |
* Hash table based implementation of the <tt>Map</tt> interface, with
|
jaroslav@1258
|
33 |
* <em>weak keys</em>.
|
jaroslav@1258
|
34 |
* An entry in a <tt>WeakHashMap</tt> will automatically be removed when
|
jaroslav@1258
|
35 |
* its key is no longer in ordinary use. More precisely, the presence of a
|
jaroslav@1258
|
36 |
* mapping for a given key will not prevent the key from being discarded by the
|
jaroslav@1258
|
37 |
* garbage collector, that is, made finalizable, finalized, and then reclaimed.
|
jaroslav@1258
|
38 |
* When a key has been discarded its entry is effectively removed from the map,
|
jaroslav@1258
|
39 |
* so this class behaves somewhat differently from other <tt>Map</tt>
|
jaroslav@1258
|
40 |
* implementations.
|
jaroslav@1258
|
41 |
*
|
jaroslav@1258
|
42 |
* <p> Both null values and the null key are supported. This class has
|
jaroslav@1258
|
43 |
* performance characteristics similar to those of the <tt>HashMap</tt>
|
jaroslav@1258
|
44 |
* class, and has the same efficiency parameters of <em>initial capacity</em>
|
jaroslav@1258
|
45 |
* and <em>load factor</em>.
|
jaroslav@1258
|
46 |
*
|
jaroslav@1258
|
47 |
* <p> Like most collection classes, this class is not synchronized.
|
jaroslav@1258
|
48 |
* A synchronized <tt>WeakHashMap</tt> may be constructed using the
|
jaroslav@1258
|
49 |
* {@link Collections#synchronizedMap Collections.synchronizedMap}
|
jaroslav@1258
|
50 |
* method.
|
jaroslav@1258
|
51 |
*
|
jaroslav@1258
|
52 |
* <p> This class is intended primarily for use with key objects whose
|
jaroslav@1258
|
53 |
* <tt>equals</tt> methods test for object identity using the
|
jaroslav@1258
|
54 |
* <tt>==</tt> operator. Once such a key is discarded it can never be
|
jaroslav@1258
|
55 |
* recreated, so it is impossible to do a lookup of that key in a
|
jaroslav@1258
|
56 |
* <tt>WeakHashMap</tt> at some later time and be surprised that its entry
|
jaroslav@1258
|
57 |
* has been removed. This class will work perfectly well with key objects
|
jaroslav@1258
|
58 |
* whose <tt>equals</tt> methods are not based upon object identity, such
|
jaroslav@1258
|
59 |
* as <tt>String</tt> instances. With such recreatable key objects,
|
jaroslav@1258
|
60 |
* however, the automatic removal of <tt>WeakHashMap</tt> entries whose
|
jaroslav@1258
|
61 |
* keys have been discarded may prove to be confusing.
|
jaroslav@1258
|
62 |
*
|
jaroslav@1258
|
63 |
* <p> The behavior of the <tt>WeakHashMap</tt> class depends in part upon
|
jaroslav@1258
|
64 |
* the actions of the garbage collector, so several familiar (though not
|
jaroslav@1258
|
65 |
* required) <tt>Map</tt> invariants do not hold for this class. Because
|
jaroslav@1258
|
66 |
* the garbage collector may discard keys at any time, a
|
jaroslav@1258
|
67 |
* <tt>WeakHashMap</tt> may behave as though an unknown thread is silently
|
jaroslav@1258
|
68 |
* removing entries. In particular, even if you synchronize on a
|
jaroslav@1258
|
69 |
* <tt>WeakHashMap</tt> instance and invoke none of its mutator methods, it
|
jaroslav@1258
|
70 |
* is possible for the <tt>size</tt> method to return smaller values over
|
jaroslav@1258
|
71 |
* time, for the <tt>isEmpty</tt> method to return <tt>false</tt> and
|
jaroslav@1258
|
72 |
* then <tt>true</tt>, for the <tt>containsKey</tt> method to return
|
jaroslav@1258
|
73 |
* <tt>true</tt> and later <tt>false</tt> for a given key, for the
|
jaroslav@1258
|
74 |
* <tt>get</tt> method to return a value for a given key but later return
|
jaroslav@1258
|
75 |
* <tt>null</tt>, for the <tt>put</tt> method to return
|
jaroslav@1258
|
76 |
* <tt>null</tt> and the <tt>remove</tt> method to return
|
jaroslav@1258
|
77 |
* <tt>false</tt> for a key that previously appeared to be in the map, and
|
jaroslav@1258
|
78 |
* for successive examinations of the key set, the value collection, and
|
jaroslav@1258
|
79 |
* the entry set to yield successively smaller numbers of elements.
|
jaroslav@1258
|
80 |
*
|
jaroslav@1258
|
81 |
* <p> Each key object in a <tt>WeakHashMap</tt> is stored indirectly as
|
jaroslav@1258
|
82 |
* the referent of a weak reference. Therefore a key will automatically be
|
jaroslav@1258
|
83 |
* removed only after the weak references to it, both inside and outside of the
|
jaroslav@1258
|
84 |
* map, have been cleared by the garbage collector.
|
jaroslav@1258
|
85 |
*
|
jaroslav@1258
|
86 |
* <p> <strong>Implementation note:</strong> The value objects in a
|
jaroslav@1258
|
87 |
* <tt>WeakHashMap</tt> are held by ordinary strong references. Thus care
|
jaroslav@1258
|
88 |
* should be taken to ensure that value objects do not strongly refer to their
|
jaroslav@1258
|
89 |
* own keys, either directly or indirectly, since that will prevent the keys
|
jaroslav@1258
|
90 |
* from being discarded. Note that a value object may refer indirectly to its
|
jaroslav@1258
|
91 |
* key via the <tt>WeakHashMap</tt> itself; that is, a value object may
|
jaroslav@1258
|
92 |
* strongly refer to some other key object whose associated value object, in
|
jaroslav@1258
|
93 |
* turn, strongly refers to the key of the first value object. One way
|
jaroslav@1258
|
94 |
* to deal with this is to wrap values themselves within
|
jaroslav@1258
|
95 |
* <tt>WeakReferences</tt> before
|
jaroslav@1258
|
96 |
* inserting, as in: <tt>m.put(key, new WeakReference(value))</tt>,
|
jaroslav@1258
|
97 |
* and then unwrapping upon each <tt>get</tt>.
|
jaroslav@1258
|
98 |
*
|
jaroslav@1258
|
99 |
* <p>The iterators returned by the <tt>iterator</tt> method of the collections
|
jaroslav@1258
|
100 |
* returned by all of this class's "collection view methods" are
|
jaroslav@1258
|
101 |
* <i>fail-fast</i>: if the map is structurally modified at any time after the
|
jaroslav@1258
|
102 |
* iterator is created, in any way except through the iterator's own
|
jaroslav@1258
|
103 |
* <tt>remove</tt> method, the iterator will throw a {@link
|
jaroslav@1258
|
104 |
* ConcurrentModificationException}. Thus, in the face of concurrent
|
jaroslav@1258
|
105 |
* modification, the iterator fails quickly and cleanly, rather than risking
|
jaroslav@1258
|
106 |
* arbitrary, non-deterministic behavior at an undetermined time in the future.
|
jaroslav@1258
|
107 |
*
|
jaroslav@1258
|
108 |
* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
|
jaroslav@1258
|
109 |
* as it is, generally speaking, impossible to make any hard guarantees in the
|
jaroslav@1258
|
110 |
* presence of unsynchronized concurrent modification. Fail-fast iterators
|
jaroslav@1258
|
111 |
* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
|
jaroslav@1258
|
112 |
* Therefore, it would be wrong to write a program that depended on this
|
jaroslav@1258
|
113 |
* exception for its correctness: <i>the fail-fast behavior of iterators
|
jaroslav@1258
|
114 |
* should be used only to detect bugs.</i>
|
jaroslav@1258
|
115 |
*
|
jaroslav@1258
|
116 |
* <p>This class is a member of the
|
jaroslav@1258
|
117 |
* <a href="{@docRoot}/../technotes/guides/collections/index.html">
|
jaroslav@1258
|
118 |
* Java Collections Framework</a>.
|
jaroslav@1258
|
119 |
*
|
jaroslav@1258
|
120 |
* @param <K> the type of keys maintained by this map
|
jaroslav@1258
|
121 |
* @param <V> the type of mapped values
|
jaroslav@1258
|
122 |
*
|
jaroslav@1258
|
123 |
* @author Doug Lea
|
jaroslav@1258
|
124 |
* @author Josh Bloch
|
jaroslav@1258
|
125 |
* @author Mark Reinhold
|
jaroslav@1258
|
126 |
* @since 1.2
|
jaroslav@1258
|
127 |
* @see java.util.HashMap
|
jaroslav@1258
|
128 |
* @see java.lang.ref.WeakReference
|
jaroslav@1258
|
129 |
*/
|
jaroslav@1258
|
130 |
public class WeakHashMap<K,V>
|
jaroslav@1258
|
131 |
extends AbstractMap<K,V>
|
jaroslav@1258
|
132 |
implements Map<K,V> {
|
jaroslav@1258
|
133 |
|
jaroslav@1258
|
134 |
/**
|
jaroslav@1258
|
135 |
* The default initial capacity -- MUST be a power of two.
|
jaroslav@1258
|
136 |
*/
|
jaroslav@1258
|
137 |
private static final int DEFAULT_INITIAL_CAPACITY = 16;
|
jaroslav@1258
|
138 |
|
jaroslav@1258
|
139 |
/**
|
jaroslav@1258
|
140 |
* The maximum capacity, used if a higher value is implicitly specified
|
jaroslav@1258
|
141 |
* by either of the constructors with arguments.
|
jaroslav@1258
|
142 |
* MUST be a power of two <= 1<<30.
|
jaroslav@1258
|
143 |
*/
|
jaroslav@1258
|
144 |
private static final int MAXIMUM_CAPACITY = 1 << 30;
|
jaroslav@1258
|
145 |
|
jaroslav@1258
|
146 |
/**
|
jaroslav@1258
|
147 |
* The load factor used when none specified in constructor.
|
jaroslav@1258
|
148 |
*/
|
jaroslav@1258
|
149 |
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
|
jaroslav@1258
|
150 |
|
jaroslav@1258
|
151 |
/**
|
jaroslav@1258
|
152 |
* The table, resized as necessary. Length MUST Always be a power of two.
|
jaroslav@1258
|
153 |
*/
|
jaroslav@1258
|
154 |
Entry<K,V>[] table;
|
jaroslav@1258
|
155 |
|
jaroslav@1258
|
156 |
/**
|
jaroslav@1258
|
157 |
* The number of key-value mappings contained in this weak hash map.
|
jaroslav@1258
|
158 |
*/
|
jaroslav@1258
|
159 |
private int size;
|
jaroslav@1258
|
160 |
|
jaroslav@1258
|
161 |
/**
|
jaroslav@1258
|
162 |
* The next size value at which to resize (capacity * load factor).
|
jaroslav@1258
|
163 |
*/
|
jaroslav@1258
|
164 |
private int threshold;
|
jaroslav@1258
|
165 |
|
jaroslav@1258
|
166 |
/**
|
jaroslav@1258
|
167 |
* The load factor for the hash table.
|
jaroslav@1258
|
168 |
*/
|
jaroslav@1258
|
169 |
private final float loadFactor;
|
jaroslav@1258
|
170 |
|
jaroslav@1258
|
171 |
/**
|
jaroslav@1258
|
172 |
* Reference queue for cleared WeakEntries
|
jaroslav@1258
|
173 |
*/
|
jaroslav@1258
|
174 |
private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
|
jaroslav@1258
|
175 |
|
jaroslav@1258
|
176 |
/**
|
jaroslav@1258
|
177 |
* The number of times this WeakHashMap has been structurally modified.
|
jaroslav@1258
|
178 |
* Structural modifications are those that change the number of
|
jaroslav@1258
|
179 |
* mappings in the map or otherwise modify its internal structure
|
jaroslav@1258
|
180 |
* (e.g., rehash). This field is used to make iterators on
|
jaroslav@1258
|
181 |
* Collection-views of the map fail-fast.
|
jaroslav@1258
|
182 |
*
|
jaroslav@1258
|
183 |
* @see ConcurrentModificationException
|
jaroslav@1258
|
184 |
*/
|
jaroslav@1258
|
185 |
int modCount;
|
jaroslav@1258
|
186 |
|
jaroslav@1258
|
187 |
@SuppressWarnings("unchecked")
|
jaroslav@1258
|
188 |
private Entry<K,V>[] newTable(int n) {
|
jaroslav@1258
|
189 |
return (Entry<K,V>[]) new Entry[n];
|
jaroslav@1258
|
190 |
}
|
jaroslav@1258
|
191 |
|
jaroslav@1258
|
192 |
/**
|
jaroslav@1258
|
193 |
* Constructs a new, empty <tt>WeakHashMap</tt> with the given initial
|
jaroslav@1258
|
194 |
* capacity and the given load factor.
|
jaroslav@1258
|
195 |
*
|
jaroslav@1258
|
196 |
* @param initialCapacity The initial capacity of the <tt>WeakHashMap</tt>
|
jaroslav@1258
|
197 |
* @param loadFactor The load factor of the <tt>WeakHashMap</tt>
|
jaroslav@1258
|
198 |
* @throws IllegalArgumentException if the initial capacity is negative,
|
jaroslav@1258
|
199 |
* or if the load factor is nonpositive.
|
jaroslav@1258
|
200 |
*/
|
jaroslav@1258
|
201 |
public WeakHashMap(int initialCapacity, float loadFactor) {
|
jaroslav@1258
|
202 |
if (initialCapacity < 0)
|
jaroslav@1258
|
203 |
throw new IllegalArgumentException("Illegal Initial Capacity: "+
|
jaroslav@1258
|
204 |
initialCapacity);
|
jaroslav@1258
|
205 |
if (initialCapacity > MAXIMUM_CAPACITY)
|
jaroslav@1258
|
206 |
initialCapacity = MAXIMUM_CAPACITY;
|
jaroslav@1258
|
207 |
|
jaroslav@1258
|
208 |
if (loadFactor <= 0 || Float.isNaN(loadFactor))
|
jaroslav@1258
|
209 |
throw new IllegalArgumentException("Illegal Load factor: "+
|
jaroslav@1258
|
210 |
loadFactor);
|
jaroslav@1258
|
211 |
int capacity = 1;
|
jaroslav@1258
|
212 |
while (capacity < initialCapacity)
|
jaroslav@1258
|
213 |
capacity <<= 1;
|
jaroslav@1258
|
214 |
table = newTable(capacity);
|
jaroslav@1258
|
215 |
this.loadFactor = loadFactor;
|
jaroslav@1258
|
216 |
threshold = (int)(capacity * loadFactor);
|
jaroslav@1258
|
217 |
}
|
jaroslav@1258
|
218 |
|
jaroslav@1258
|
219 |
/**
|
jaroslav@1258
|
220 |
* Constructs a new, empty <tt>WeakHashMap</tt> with the given initial
|
jaroslav@1258
|
221 |
* capacity and the default load factor (0.75).
|
jaroslav@1258
|
222 |
*
|
jaroslav@1258
|
223 |
* @param initialCapacity The initial capacity of the <tt>WeakHashMap</tt>
|
jaroslav@1258
|
224 |
* @throws IllegalArgumentException if the initial capacity is negative
|
jaroslav@1258
|
225 |
*/
|
jaroslav@1258
|
226 |
public WeakHashMap(int initialCapacity) {
|
jaroslav@1258
|
227 |
this(initialCapacity, DEFAULT_LOAD_FACTOR);
|
jaroslav@1258
|
228 |
}
|
jaroslav@1258
|
229 |
|
jaroslav@1258
|
230 |
/**
|
jaroslav@1258
|
231 |
* Constructs a new, empty <tt>WeakHashMap</tt> with the default initial
|
jaroslav@1258
|
232 |
* capacity (16) and load factor (0.75).
|
jaroslav@1258
|
233 |
*/
|
jaroslav@1258
|
234 |
public WeakHashMap() {
|
jaroslav@1258
|
235 |
this.loadFactor = DEFAULT_LOAD_FACTOR;
|
jaroslav@1258
|
236 |
threshold = DEFAULT_INITIAL_CAPACITY;
|
jaroslav@1258
|
237 |
table = newTable(DEFAULT_INITIAL_CAPACITY);
|
jaroslav@1258
|
238 |
}
|
jaroslav@1258
|
239 |
|
jaroslav@1258
|
240 |
/**
|
jaroslav@1258
|
241 |
* Constructs a new <tt>WeakHashMap</tt> with the same mappings as the
|
jaroslav@1258
|
242 |
* specified map. The <tt>WeakHashMap</tt> is created with the default
|
jaroslav@1258
|
243 |
* load factor (0.75) and an initial capacity sufficient to hold the
|
jaroslav@1258
|
244 |
* mappings in the specified map.
|
jaroslav@1258
|
245 |
*
|
jaroslav@1258
|
246 |
* @param m the map whose mappings are to be placed in this map
|
jaroslav@1258
|
247 |
* @throws NullPointerException if the specified map is null
|
jaroslav@1258
|
248 |
* @since 1.3
|
jaroslav@1258
|
249 |
*/
|
jaroslav@1258
|
250 |
public WeakHashMap(Map<? extends K, ? extends V> m) {
|
jaroslav@1258
|
251 |
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, 16),
|
jaroslav@1258
|
252 |
DEFAULT_LOAD_FACTOR);
|
jaroslav@1258
|
253 |
putAll(m);
|
jaroslav@1258
|
254 |
}
|
jaroslav@1258
|
255 |
|
jaroslav@1258
|
256 |
// internal utilities
|
jaroslav@1258
|
257 |
|
jaroslav@1258
|
258 |
/**
|
jaroslav@1258
|
259 |
* Value representing null keys inside tables.
|
jaroslav@1258
|
260 |
*/
|
jaroslav@1258
|
261 |
private static final Object NULL_KEY = new Object();
|
jaroslav@1258
|
262 |
|
jaroslav@1258
|
263 |
/**
|
jaroslav@1258
|
264 |
* Use NULL_KEY for key if it is null.
|
jaroslav@1258
|
265 |
*/
|
jaroslav@1258
|
266 |
private static Object maskNull(Object key) {
|
jaroslav@1258
|
267 |
return (key == null) ? NULL_KEY : key;
|
jaroslav@1258
|
268 |
}
|
jaroslav@1258
|
269 |
|
jaroslav@1258
|
270 |
/**
|
jaroslav@1258
|
271 |
* Returns internal representation of null key back to caller as null.
|
jaroslav@1258
|
272 |
*/
|
jaroslav@1258
|
273 |
static Object unmaskNull(Object key) {
|
jaroslav@1258
|
274 |
return (key == NULL_KEY) ? null : key;
|
jaroslav@1258
|
275 |
}
|
jaroslav@1258
|
276 |
|
jaroslav@1258
|
277 |
/**
|
jaroslav@1258
|
278 |
* Checks for equality of non-null reference x and possibly-null y. By
|
jaroslav@1258
|
279 |
* default uses Object.equals.
|
jaroslav@1258
|
280 |
*/
|
jaroslav@1258
|
281 |
private static boolean eq(Object x, Object y) {
|
jaroslav@1258
|
282 |
return x == y || x.equals(y);
|
jaroslav@1258
|
283 |
}
|
jaroslav@1258
|
284 |
|
jaroslav@1258
|
285 |
/**
|
jaroslav@1258
|
286 |
* Returns index for hash code h.
|
jaroslav@1258
|
287 |
*/
|
jaroslav@1258
|
288 |
private static int indexFor(int h, int length) {
|
jaroslav@1258
|
289 |
return h & (length-1);
|
jaroslav@1258
|
290 |
}
|
jaroslav@1258
|
291 |
|
jaroslav@1258
|
292 |
/**
|
jaroslav@1258
|
293 |
* Expunges stale entries from the table.
|
jaroslav@1258
|
294 |
*/
|
jaroslav@1258
|
295 |
private void expungeStaleEntries() {
|
jaroslav@1258
|
296 |
for (Object x; (x = queue.poll()) != null; ) {
|
jaroslav@1258
|
297 |
synchronized (queue) {
|
jaroslav@1258
|
298 |
@SuppressWarnings("unchecked")
|
jaroslav@1258
|
299 |
Entry<K,V> e = (Entry<K,V>) x;
|
jaroslav@1258
|
300 |
int i = indexFor(e.hash, table.length);
|
jaroslav@1258
|
301 |
|
jaroslav@1258
|
302 |
Entry<K,V> prev = table[i];
|
jaroslav@1258
|
303 |
Entry<K,V> p = prev;
|
jaroslav@1258
|
304 |
while (p != null) {
|
jaroslav@1258
|
305 |
Entry<K,V> next = p.next;
|
jaroslav@1258
|
306 |
if (p == e) {
|
jaroslav@1258
|
307 |
if (prev == e)
|
jaroslav@1258
|
308 |
table[i] = next;
|
jaroslav@1258
|
309 |
else
|
jaroslav@1258
|
310 |
prev.next = next;
|
jaroslav@1258
|
311 |
// Must not null out e.next;
|
jaroslav@1258
|
312 |
// stale entries may be in use by a HashIterator
|
jaroslav@1258
|
313 |
e.value = null; // Help GC
|
jaroslav@1258
|
314 |
size--;
|
jaroslav@1258
|
315 |
break;
|
jaroslav@1258
|
316 |
}
|
jaroslav@1258
|
317 |
prev = p;
|
jaroslav@1258
|
318 |
p = next;
|
jaroslav@1258
|
319 |
}
|
jaroslav@1258
|
320 |
}
|
jaroslav@1258
|
321 |
}
|
jaroslav@1258
|
322 |
}
|
jaroslav@1258
|
323 |
|
jaroslav@1258
|
324 |
/**
|
jaroslav@1258
|
325 |
* Returns the table after first expunging stale entries.
|
jaroslav@1258
|
326 |
*/
|
jaroslav@1258
|
327 |
private Entry<K,V>[] getTable() {
|
jaroslav@1258
|
328 |
expungeStaleEntries();
|
jaroslav@1258
|
329 |
return table;
|
jaroslav@1258
|
330 |
}
|
jaroslav@1258
|
331 |
|
jaroslav@1258
|
332 |
/**
|
jaroslav@1258
|
333 |
* Returns the number of key-value mappings in this map.
|
jaroslav@1258
|
334 |
* This result is a snapshot, and may not reflect unprocessed
|
jaroslav@1258
|
335 |
* entries that will be removed before next attempted access
|
jaroslav@1258
|
336 |
* because they are no longer referenced.
|
jaroslav@1258
|
337 |
*/
|
jaroslav@1258
|
338 |
public int size() {
|
jaroslav@1258
|
339 |
if (size == 0)
|
jaroslav@1258
|
340 |
return 0;
|
jaroslav@1258
|
341 |
expungeStaleEntries();
|
jaroslav@1258
|
342 |
return size;
|
jaroslav@1258
|
343 |
}
|
jaroslav@1258
|
344 |
|
jaroslav@1258
|
345 |
/**
|
jaroslav@1258
|
346 |
* Returns <tt>true</tt> if this map contains no key-value mappings.
|
jaroslav@1258
|
347 |
* This result is a snapshot, and may not reflect unprocessed
|
jaroslav@1258
|
348 |
* entries that will be removed before next attempted access
|
jaroslav@1258
|
349 |
* because they are no longer referenced.
|
jaroslav@1258
|
350 |
*/
|
jaroslav@1258
|
351 |
public boolean isEmpty() {
|
jaroslav@1258
|
352 |
return size() == 0;
|
jaroslav@1258
|
353 |
}
|
jaroslav@1258
|
354 |
|
jaroslav@1258
|
355 |
/**
|
jaroslav@1258
|
356 |
* Returns the value to which the specified key is mapped,
|
jaroslav@1258
|
357 |
* or {@code null} if this map contains no mapping for the key.
|
jaroslav@1258
|
358 |
*
|
jaroslav@1258
|
359 |
* <p>More formally, if this map contains a mapping from a key
|
jaroslav@1258
|
360 |
* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
|
jaroslav@1258
|
361 |
* key.equals(k))}, then this method returns {@code v}; otherwise
|
jaroslav@1258
|
362 |
* it returns {@code null}. (There can be at most one such mapping.)
|
jaroslav@1258
|
363 |
*
|
jaroslav@1258
|
364 |
* <p>A return value of {@code null} does not <i>necessarily</i>
|
jaroslav@1258
|
365 |
* indicate that the map contains no mapping for the key; it's also
|
jaroslav@1258
|
366 |
* possible that the map explicitly maps the key to {@code null}.
|
jaroslav@1258
|
367 |
* The {@link #containsKey containsKey} operation may be used to
|
jaroslav@1258
|
368 |
* distinguish these two cases.
|
jaroslav@1258
|
369 |
*
|
jaroslav@1258
|
370 |
* @see #put(Object, Object)
|
jaroslav@1258
|
371 |
*/
|
jaroslav@1258
|
372 |
public V get(Object key) {
|
jaroslav@1258
|
373 |
Object k = maskNull(key);
|
jaroslav@1258
|
374 |
int h = HashMap.hash(k.hashCode());
|
jaroslav@1258
|
375 |
Entry<K,V>[] tab = getTable();
|
jaroslav@1258
|
376 |
int index = indexFor(h, tab.length);
|
jaroslav@1258
|
377 |
Entry<K,V> e = tab[index];
|
jaroslav@1258
|
378 |
while (e != null) {
|
jaroslav@1258
|
379 |
if (e.hash == h && eq(k, e.get()))
|
jaroslav@1258
|
380 |
return e.value;
|
jaroslav@1258
|
381 |
e = e.next;
|
jaroslav@1258
|
382 |
}
|
jaroslav@1258
|
383 |
return null;
|
jaroslav@1258
|
384 |
}
|
jaroslav@1258
|
385 |
|
jaroslav@1258
|
386 |
/**
|
jaroslav@1258
|
387 |
* Returns <tt>true</tt> if this map contains a mapping for the
|
jaroslav@1258
|
388 |
* specified key.
|
jaroslav@1258
|
389 |
*
|
jaroslav@1258
|
390 |
* @param key The key whose presence in this map is to be tested
|
jaroslav@1258
|
391 |
* @return <tt>true</tt> if there is a mapping for <tt>key</tt>;
|
jaroslav@1258
|
392 |
* <tt>false</tt> otherwise
|
jaroslav@1258
|
393 |
*/
|
jaroslav@1258
|
394 |
public boolean containsKey(Object key) {
|
jaroslav@1258
|
395 |
return getEntry(key) != null;
|
jaroslav@1258
|
396 |
}
|
jaroslav@1258
|
397 |
|
jaroslav@1258
|
398 |
/**
|
jaroslav@1258
|
399 |
* Returns the entry associated with the specified key in this map.
|
jaroslav@1258
|
400 |
* Returns null if the map contains no mapping for this key.
|
jaroslav@1258
|
401 |
*/
|
jaroslav@1258
|
402 |
Entry<K,V> getEntry(Object key) {
|
jaroslav@1258
|
403 |
Object k = maskNull(key);
|
jaroslav@1258
|
404 |
int h = HashMap.hash(k.hashCode());
|
jaroslav@1258
|
405 |
Entry<K,V>[] tab = getTable();
|
jaroslav@1258
|
406 |
int index = indexFor(h, tab.length);
|
jaroslav@1258
|
407 |
Entry<K,V> e = tab[index];
|
jaroslav@1258
|
408 |
while (e != null && !(e.hash == h && eq(k, e.get())))
|
jaroslav@1258
|
409 |
e = e.next;
|
jaroslav@1258
|
410 |
return e;
|
jaroslav@1258
|
411 |
}
|
jaroslav@1258
|
412 |
|
jaroslav@1258
|
413 |
/**
|
jaroslav@1258
|
414 |
* Associates the specified value with the specified key in this map.
|
jaroslav@1258
|
415 |
* If the map previously contained a mapping for this key, the old
|
jaroslav@1258
|
416 |
* value is replaced.
|
jaroslav@1258
|
417 |
*
|
jaroslav@1258
|
418 |
* @param key key with which the specified value is to be associated.
|
jaroslav@1258
|
419 |
* @param value value to be associated with the specified key.
|
jaroslav@1258
|
420 |
* @return the previous value associated with <tt>key</tt>, or
|
jaroslav@1258
|
421 |
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
|
jaroslav@1258
|
422 |
* (A <tt>null</tt> return can also indicate that the map
|
jaroslav@1258
|
423 |
* previously associated <tt>null</tt> with <tt>key</tt>.)
|
jaroslav@1258
|
424 |
*/
|
jaroslav@1258
|
425 |
public V put(K key, V value) {
|
jaroslav@1258
|
426 |
Object k = maskNull(key);
|
jaroslav@1258
|
427 |
int h = HashMap.hash(k.hashCode());
|
jaroslav@1258
|
428 |
Entry<K,V>[] tab = getTable();
|
jaroslav@1258
|
429 |
int i = indexFor(h, tab.length);
|
jaroslav@1258
|
430 |
|
jaroslav@1258
|
431 |
for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
|
jaroslav@1258
|
432 |
if (h == e.hash && eq(k, e.get())) {
|
jaroslav@1258
|
433 |
V oldValue = e.value;
|
jaroslav@1258
|
434 |
if (value != oldValue)
|
jaroslav@1258
|
435 |
e.value = value;
|
jaroslav@1258
|
436 |
return oldValue;
|
jaroslav@1258
|
437 |
}
|
jaroslav@1258
|
438 |
}
|
jaroslav@1258
|
439 |
|
jaroslav@1258
|
440 |
modCount++;
|
jaroslav@1258
|
441 |
Entry<K,V> e = tab[i];
|
jaroslav@1258
|
442 |
tab[i] = new Entry<>(k, value, queue, h, e);
|
jaroslav@1258
|
443 |
if (++size >= threshold)
|
jaroslav@1258
|
444 |
resize(tab.length * 2);
|
jaroslav@1258
|
445 |
return null;
|
jaroslav@1258
|
446 |
}
|
jaroslav@1258
|
447 |
|
jaroslav@1258
|
448 |
/**
|
jaroslav@1258
|
449 |
* Rehashes the contents of this map into a new array with a
|
jaroslav@1258
|
450 |
* larger capacity. This method is called automatically when the
|
jaroslav@1258
|
451 |
* number of keys in this map reaches its threshold.
|
jaroslav@1258
|
452 |
*
|
jaroslav@1258
|
453 |
* If current capacity is MAXIMUM_CAPACITY, this method does not
|
jaroslav@1258
|
454 |
* resize the map, but sets threshold to Integer.MAX_VALUE.
|
jaroslav@1258
|
455 |
* This has the effect of preventing future calls.
|
jaroslav@1258
|
456 |
*
|
jaroslav@1258
|
457 |
* @param newCapacity the new capacity, MUST be a power of two;
|
jaroslav@1258
|
458 |
* must be greater than current capacity unless current
|
jaroslav@1258
|
459 |
* capacity is MAXIMUM_CAPACITY (in which case value
|
jaroslav@1258
|
460 |
* is irrelevant).
|
jaroslav@1258
|
461 |
*/
|
jaroslav@1258
|
462 |
void resize(int newCapacity) {
|
jaroslav@1258
|
463 |
Entry<K,V>[] oldTable = getTable();
|
jaroslav@1258
|
464 |
int oldCapacity = oldTable.length;
|
jaroslav@1258
|
465 |
if (oldCapacity == MAXIMUM_CAPACITY) {
|
jaroslav@1258
|
466 |
threshold = Integer.MAX_VALUE;
|
jaroslav@1258
|
467 |
return;
|
jaroslav@1258
|
468 |
}
|
jaroslav@1258
|
469 |
|
jaroslav@1258
|
470 |
Entry<K,V>[] newTable = newTable(newCapacity);
|
jaroslav@1258
|
471 |
transfer(oldTable, newTable);
|
jaroslav@1258
|
472 |
table = newTable;
|
jaroslav@1258
|
473 |
|
jaroslav@1258
|
474 |
/*
|
jaroslav@1258
|
475 |
* If ignoring null elements and processing ref queue caused massive
|
jaroslav@1258
|
476 |
* shrinkage, then restore old table. This should be rare, but avoids
|
jaroslav@1258
|
477 |
* unbounded expansion of garbage-filled tables.
|
jaroslav@1258
|
478 |
*/
|
jaroslav@1258
|
479 |
if (size >= threshold / 2) {
|
jaroslav@1258
|
480 |
threshold = (int)(newCapacity * loadFactor);
|
jaroslav@1258
|
481 |
} else {
|
jaroslav@1258
|
482 |
expungeStaleEntries();
|
jaroslav@1258
|
483 |
transfer(newTable, oldTable);
|
jaroslav@1258
|
484 |
table = oldTable;
|
jaroslav@1258
|
485 |
}
|
jaroslav@1258
|
486 |
}
|
jaroslav@1258
|
487 |
|
jaroslav@1258
|
488 |
/** Transfers all entries from src to dest tables */
|
jaroslav@1258
|
489 |
private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) {
|
jaroslav@1258
|
490 |
for (int j = 0; j < src.length; ++j) {
|
jaroslav@1258
|
491 |
Entry<K,V> e = src[j];
|
jaroslav@1258
|
492 |
src[j] = null;
|
jaroslav@1258
|
493 |
while (e != null) {
|
jaroslav@1258
|
494 |
Entry<K,V> next = e.next;
|
jaroslav@1258
|
495 |
Object key = e.get();
|
jaroslav@1258
|
496 |
if (key == null) {
|
jaroslav@1258
|
497 |
e.next = null; // Help GC
|
jaroslav@1258
|
498 |
e.value = null; // " "
|
jaroslav@1258
|
499 |
size--;
|
jaroslav@1258
|
500 |
} else {
|
jaroslav@1258
|
501 |
int i = indexFor(e.hash, dest.length);
|
jaroslav@1258
|
502 |
e.next = dest[i];
|
jaroslav@1258
|
503 |
dest[i] = e;
|
jaroslav@1258
|
504 |
}
|
jaroslav@1258
|
505 |
e = next;
|
jaroslav@1258
|
506 |
}
|
jaroslav@1258
|
507 |
}
|
jaroslav@1258
|
508 |
}
|
jaroslav@1258
|
509 |
|
jaroslav@1258
|
510 |
/**
|
jaroslav@1258
|
511 |
* Copies all of the mappings from the specified map to this map.
|
jaroslav@1258
|
512 |
* These mappings will replace any mappings that this map had for any
|
jaroslav@1258
|
513 |
* of the keys currently in the specified map.
|
jaroslav@1258
|
514 |
*
|
jaroslav@1258
|
515 |
* @param m mappings to be stored in this map.
|
jaroslav@1258
|
516 |
* @throws NullPointerException if the specified map is null.
|
jaroslav@1258
|
517 |
*/
|
jaroslav@1258
|
518 |
public void putAll(Map<? extends K, ? extends V> m) {
|
jaroslav@1258
|
519 |
int numKeysToBeAdded = m.size();
|
jaroslav@1258
|
520 |
if (numKeysToBeAdded == 0)
|
jaroslav@1258
|
521 |
return;
|
jaroslav@1258
|
522 |
|
jaroslav@1258
|
523 |
/*
|
jaroslav@1258
|
524 |
* Expand the map if the map if the number of mappings to be added
|
jaroslav@1258
|
525 |
* is greater than or equal to threshold. This is conservative; the
|
jaroslav@1258
|
526 |
* obvious condition is (m.size() + size) >= threshold, but this
|
jaroslav@1258
|
527 |
* condition could result in a map with twice the appropriate capacity,
|
jaroslav@1258
|
528 |
* if the keys to be added overlap with the keys already in this map.
|
jaroslav@1258
|
529 |
* By using the conservative calculation, we subject ourself
|
jaroslav@1258
|
530 |
* to at most one extra resize.
|
jaroslav@1258
|
531 |
*/
|
jaroslav@1258
|
532 |
if (numKeysToBeAdded > threshold) {
|
jaroslav@1258
|
533 |
int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
|
jaroslav@1258
|
534 |
if (targetCapacity > MAXIMUM_CAPACITY)
|
jaroslav@1258
|
535 |
targetCapacity = MAXIMUM_CAPACITY;
|
jaroslav@1258
|
536 |
int newCapacity = table.length;
|
jaroslav@1258
|
537 |
while (newCapacity < targetCapacity)
|
jaroslav@1258
|
538 |
newCapacity <<= 1;
|
jaroslav@1258
|
539 |
if (newCapacity > table.length)
|
jaroslav@1258
|
540 |
resize(newCapacity);
|
jaroslav@1258
|
541 |
}
|
jaroslav@1258
|
542 |
|
jaroslav@1258
|
543 |
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
|
jaroslav@1258
|
544 |
put(e.getKey(), e.getValue());
|
jaroslav@1258
|
545 |
}
|
jaroslav@1258
|
546 |
|
jaroslav@1258
|
547 |
/**
|
jaroslav@1258
|
548 |
* Removes the mapping for a key from this weak hash map if it is present.
|
jaroslav@1258
|
549 |
* More formally, if this map contains a mapping from key <tt>k</tt> to
|
jaroslav@1258
|
550 |
* value <tt>v</tt> such that <code>(key==null ? k==null :
|
jaroslav@1258
|
551 |
* key.equals(k))</code>, that mapping is removed. (The map can contain
|
jaroslav@1258
|
552 |
* at most one such mapping.)
|
jaroslav@1258
|
553 |
*
|
jaroslav@1258
|
554 |
* <p>Returns the value to which this map previously associated the key,
|
jaroslav@1258
|
555 |
* or <tt>null</tt> if the map contained no mapping for the key. A
|
jaroslav@1258
|
556 |
* return value of <tt>null</tt> does not <i>necessarily</i> indicate
|
jaroslav@1258
|
557 |
* that the map contained no mapping for the key; it's also possible
|
jaroslav@1258
|
558 |
* that the map explicitly mapped the key to <tt>null</tt>.
|
jaroslav@1258
|
559 |
*
|
jaroslav@1258
|
560 |
* <p>The map will not contain a mapping for the specified key once the
|
jaroslav@1258
|
561 |
* call returns.
|
jaroslav@1258
|
562 |
*
|
jaroslav@1258
|
563 |
* @param key key whose mapping is to be removed from the map
|
jaroslav@1258
|
564 |
* @return the previous value associated with <tt>key</tt>, or
|
jaroslav@1258
|
565 |
* <tt>null</tt> if there was no mapping for <tt>key</tt>
|
jaroslav@1258
|
566 |
*/
|
jaroslav@1258
|
567 |
public V remove(Object key) {
|
jaroslav@1258
|
568 |
Object k = maskNull(key);
|
jaroslav@1258
|
569 |
int h = HashMap.hash(k.hashCode());
|
jaroslav@1258
|
570 |
Entry<K,V>[] tab = getTable();
|
jaroslav@1258
|
571 |
int i = indexFor(h, tab.length);
|
jaroslav@1258
|
572 |
Entry<K,V> prev = tab[i];
|
jaroslav@1258
|
573 |
Entry<K,V> e = prev;
|
jaroslav@1258
|
574 |
|
jaroslav@1258
|
575 |
while (e != null) {
|
jaroslav@1258
|
576 |
Entry<K,V> next = e.next;
|
jaroslav@1258
|
577 |
if (h == e.hash && eq(k, e.get())) {
|
jaroslav@1258
|
578 |
modCount++;
|
jaroslav@1258
|
579 |
size--;
|
jaroslav@1258
|
580 |
if (prev == e)
|
jaroslav@1258
|
581 |
tab[i] = next;
|
jaroslav@1258
|
582 |
else
|
jaroslav@1258
|
583 |
prev.next = next;
|
jaroslav@1258
|
584 |
return e.value;
|
jaroslav@1258
|
585 |
}
|
jaroslav@1258
|
586 |
prev = e;
|
jaroslav@1258
|
587 |
e = next;
|
jaroslav@1258
|
588 |
}
|
jaroslav@1258
|
589 |
|
jaroslav@1258
|
590 |
return null;
|
jaroslav@1258
|
591 |
}
|
jaroslav@1258
|
592 |
|
jaroslav@1258
|
593 |
/** Special version of remove needed by Entry set */
|
jaroslav@1258
|
594 |
boolean removeMapping(Object o) {
|
jaroslav@1258
|
595 |
if (!(o instanceof Map.Entry))
|
jaroslav@1258
|
596 |
return false;
|
jaroslav@1258
|
597 |
Entry<K,V>[] tab = getTable();
|
jaroslav@1258
|
598 |
Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
|
jaroslav@1258
|
599 |
Object k = maskNull(entry.getKey());
|
jaroslav@1258
|
600 |
int h = HashMap.hash(k.hashCode());
|
jaroslav@1258
|
601 |
int i = indexFor(h, tab.length);
|
jaroslav@1258
|
602 |
Entry<K,V> prev = tab[i];
|
jaroslav@1258
|
603 |
Entry<K,V> e = prev;
|
jaroslav@1258
|
604 |
|
jaroslav@1258
|
605 |
while (e != null) {
|
jaroslav@1258
|
606 |
Entry<K,V> next = e.next;
|
jaroslav@1258
|
607 |
if (h == e.hash && e.equals(entry)) {
|
jaroslav@1258
|
608 |
modCount++;
|
jaroslav@1258
|
609 |
size--;
|
jaroslav@1258
|
610 |
if (prev == e)
|
jaroslav@1258
|
611 |
tab[i] = next;
|
jaroslav@1258
|
612 |
else
|
jaroslav@1258
|
613 |
prev.next = next;
|
jaroslav@1258
|
614 |
return true;
|
jaroslav@1258
|
615 |
}
|
jaroslav@1258
|
616 |
prev = e;
|
jaroslav@1258
|
617 |
e = next;
|
jaroslav@1258
|
618 |
}
|
jaroslav@1258
|
619 |
|
jaroslav@1258
|
620 |
return false;
|
jaroslav@1258
|
621 |
}
|
jaroslav@1258
|
622 |
|
jaroslav@1258
|
623 |
/**
|
jaroslav@1258
|
624 |
* Removes all of the mappings from this map.
|
jaroslav@1258
|
625 |
* The map will be empty after this call returns.
|
jaroslav@1258
|
626 |
*/
|
jaroslav@1258
|
627 |
public void clear() {
|
jaroslav@1258
|
628 |
// clear out ref queue. We don't need to expunge entries
|
jaroslav@1258
|
629 |
// since table is getting cleared.
|
jaroslav@1258
|
630 |
while (queue.poll() != null)
|
jaroslav@1258
|
631 |
;
|
jaroslav@1258
|
632 |
|
jaroslav@1258
|
633 |
modCount++;
|
jaroslav@1258
|
634 |
Arrays.fill(table, null);
|
jaroslav@1258
|
635 |
size = 0;
|
jaroslav@1258
|
636 |
|
jaroslav@1258
|
637 |
// Allocation of array may have caused GC, which may have caused
|
jaroslav@1258
|
638 |
// additional entries to go stale. Removing these entries from the
|
jaroslav@1258
|
639 |
// reference queue will make them eligible for reclamation.
|
jaroslav@1258
|
640 |
while (queue.poll() != null)
|
jaroslav@1258
|
641 |
;
|
jaroslav@1258
|
642 |
}
|
jaroslav@1258
|
643 |
|
jaroslav@1258
|
644 |
/**
|
jaroslav@1258
|
645 |
* Returns <tt>true</tt> if this map maps one or more keys to the
|
jaroslav@1258
|
646 |
* specified value.
|
jaroslav@1258
|
647 |
*
|
jaroslav@1258
|
648 |
* @param value value whose presence in this map is to be tested
|
jaroslav@1258
|
649 |
* @return <tt>true</tt> if this map maps one or more keys to the
|
jaroslav@1258
|
650 |
* specified value
|
jaroslav@1258
|
651 |
*/
|
jaroslav@1258
|
652 |
public boolean containsValue(Object value) {
|
jaroslav@1258
|
653 |
if (value==null)
|
jaroslav@1258
|
654 |
return containsNullValue();
|
jaroslav@1258
|
655 |
|
jaroslav@1258
|
656 |
Entry<K,V>[] tab = getTable();
|
jaroslav@1258
|
657 |
for (int i = tab.length; i-- > 0;)
|
jaroslav@1258
|
658 |
for (Entry<K,V> e = tab[i]; e != null; e = e.next)
|
jaroslav@1258
|
659 |
if (value.equals(e.value))
|
jaroslav@1258
|
660 |
return true;
|
jaroslav@1258
|
661 |
return false;
|
jaroslav@1258
|
662 |
}
|
jaroslav@1258
|
663 |
|
jaroslav@1258
|
664 |
/**
|
jaroslav@1258
|
665 |
* Special-case code for containsValue with null argument
|
jaroslav@1258
|
666 |
*/
|
jaroslav@1258
|
667 |
private boolean containsNullValue() {
|
jaroslav@1258
|
668 |
Entry<K,V>[] tab = getTable();
|
jaroslav@1258
|
669 |
for (int i = tab.length; i-- > 0;)
|
jaroslav@1258
|
670 |
for (Entry<K,V> e = tab[i]; e != null; e = e.next)
|
jaroslav@1258
|
671 |
if (e.value==null)
|
jaroslav@1258
|
672 |
return true;
|
jaroslav@1258
|
673 |
return false;
|
jaroslav@1258
|
674 |
}
|
jaroslav@1258
|
675 |
|
jaroslav@1258
|
676 |
/**
|
jaroslav@1258
|
677 |
* The entries in this hash table extend WeakReference, using its main ref
|
jaroslav@1258
|
678 |
* field as the key.
|
jaroslav@1258
|
679 |
*/
|
jaroslav@1258
|
680 |
private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
|
jaroslav@1258
|
681 |
V value;
|
jaroslav@1258
|
682 |
final int hash;
|
jaroslav@1258
|
683 |
Entry<K,V> next;
|
jaroslav@1258
|
684 |
|
jaroslav@1258
|
685 |
/**
|
jaroslav@1258
|
686 |
* Creates new entry.
|
jaroslav@1258
|
687 |
*/
|
jaroslav@1258
|
688 |
Entry(Object key, V value,
|
jaroslav@1258
|
689 |
ReferenceQueue<Object> queue,
|
jaroslav@1258
|
690 |
int hash, Entry<K,V> next) {
|
jaroslav@1258
|
691 |
super(key, queue);
|
jaroslav@1258
|
692 |
this.value = value;
|
jaroslav@1258
|
693 |
this.hash = hash;
|
jaroslav@1258
|
694 |
this.next = next;
|
jaroslav@1258
|
695 |
}
|
jaroslav@1258
|
696 |
|
jaroslav@1258
|
697 |
@SuppressWarnings("unchecked")
|
jaroslav@1258
|
698 |
public K getKey() {
|
jaroslav@1258
|
699 |
return (K) WeakHashMap.unmaskNull(get());
|
jaroslav@1258
|
700 |
}
|
jaroslav@1258
|
701 |
|
jaroslav@1258
|
702 |
public V getValue() {
|
jaroslav@1258
|
703 |
return value;
|
jaroslav@1258
|
704 |
}
|
jaroslav@1258
|
705 |
|
jaroslav@1258
|
706 |
public V setValue(V newValue) {
|
jaroslav@1258
|
707 |
V oldValue = value;
|
jaroslav@1258
|
708 |
value = newValue;
|
jaroslav@1258
|
709 |
return oldValue;
|
jaroslav@1258
|
710 |
}
|
jaroslav@1258
|
711 |
|
jaroslav@1258
|
712 |
public boolean equals(Object o) {
|
jaroslav@1258
|
713 |
if (!(o instanceof Map.Entry))
|
jaroslav@1258
|
714 |
return false;
|
jaroslav@1258
|
715 |
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
|
jaroslav@1258
|
716 |
K k1 = getKey();
|
jaroslav@1258
|
717 |
Object k2 = e.getKey();
|
jaroslav@1258
|
718 |
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
|
jaroslav@1258
|
719 |
V v1 = getValue();
|
jaroslav@1258
|
720 |
Object v2 = e.getValue();
|
jaroslav@1258
|
721 |
if (v1 == v2 || (v1 != null && v1.equals(v2)))
|
jaroslav@1258
|
722 |
return true;
|
jaroslav@1258
|
723 |
}
|
jaroslav@1258
|
724 |
return false;
|
jaroslav@1258
|
725 |
}
|
jaroslav@1258
|
726 |
|
jaroslav@1258
|
727 |
public int hashCode() {
|
jaroslav@1258
|
728 |
K k = getKey();
|
jaroslav@1258
|
729 |
V v = getValue();
|
jaroslav@1258
|
730 |
return ((k==null ? 0 : k.hashCode()) ^
|
jaroslav@1258
|
731 |
(v==null ? 0 : v.hashCode()));
|
jaroslav@1258
|
732 |
}
|
jaroslav@1258
|
733 |
|
jaroslav@1258
|
734 |
public String toString() {
|
jaroslav@1258
|
735 |
return getKey() + "=" + getValue();
|
jaroslav@1258
|
736 |
}
|
jaroslav@1258
|
737 |
}
|
jaroslav@1258
|
738 |
|
jaroslav@1258
|
739 |
private abstract class HashIterator<T> implements Iterator<T> {
|
jaroslav@1258
|
740 |
private int index;
|
jaroslav@1258
|
741 |
private Entry<K,V> entry = null;
|
jaroslav@1258
|
742 |
private Entry<K,V> lastReturned = null;
|
jaroslav@1258
|
743 |
private int expectedModCount = modCount;
|
jaroslav@1258
|
744 |
|
jaroslav@1258
|
745 |
/**
|
jaroslav@1258
|
746 |
* Strong reference needed to avoid disappearance of key
|
jaroslav@1258
|
747 |
* between hasNext and next
|
jaroslav@1258
|
748 |
*/
|
jaroslav@1258
|
749 |
private Object nextKey = null;
|
jaroslav@1258
|
750 |
|
jaroslav@1258
|
751 |
/**
|
jaroslav@1258
|
752 |
* Strong reference needed to avoid disappearance of key
|
jaroslav@1258
|
753 |
* between nextEntry() and any use of the entry
|
jaroslav@1258
|
754 |
*/
|
jaroslav@1258
|
755 |
private Object currentKey = null;
|
jaroslav@1258
|
756 |
|
jaroslav@1258
|
757 |
HashIterator() {
|
jaroslav@1258
|
758 |
index = isEmpty() ? 0 : table.length;
|
jaroslav@1258
|
759 |
}
|
jaroslav@1258
|
760 |
|
jaroslav@1258
|
761 |
public boolean hasNext() {
|
jaroslav@1258
|
762 |
Entry<K,V>[] t = table;
|
jaroslav@1258
|
763 |
|
jaroslav@1258
|
764 |
while (nextKey == null) {
|
jaroslav@1258
|
765 |
Entry<K,V> e = entry;
|
jaroslav@1258
|
766 |
int i = index;
|
jaroslav@1258
|
767 |
while (e == null && i > 0)
|
jaroslav@1258
|
768 |
e = t[--i];
|
jaroslav@1258
|
769 |
entry = e;
|
jaroslav@1258
|
770 |
index = i;
|
jaroslav@1258
|
771 |
if (e == null) {
|
jaroslav@1258
|
772 |
currentKey = null;
|
jaroslav@1258
|
773 |
return false;
|
jaroslav@1258
|
774 |
}
|
jaroslav@1258
|
775 |
nextKey = e.get(); // hold on to key in strong ref
|
jaroslav@1258
|
776 |
if (nextKey == null)
|
jaroslav@1258
|
777 |
entry = entry.next;
|
jaroslav@1258
|
778 |
}
|
jaroslav@1258
|
779 |
return true;
|
jaroslav@1258
|
780 |
}
|
jaroslav@1258
|
781 |
|
jaroslav@1258
|
782 |
/** The common parts of next() across different types of iterators */
|
jaroslav@1258
|
783 |
protected Entry<K,V> nextEntry() {
|
jaroslav@1258
|
784 |
if (modCount != expectedModCount)
|
jaroslav@1258
|
785 |
throw new ConcurrentModificationException();
|
jaroslav@1258
|
786 |
if (nextKey == null && !hasNext())
|
jaroslav@1258
|
787 |
throw new NoSuchElementException();
|
jaroslav@1258
|
788 |
|
jaroslav@1258
|
789 |
lastReturned = entry;
|
jaroslav@1258
|
790 |
entry = entry.next;
|
jaroslav@1258
|
791 |
currentKey = nextKey;
|
jaroslav@1258
|
792 |
nextKey = null;
|
jaroslav@1258
|
793 |
return lastReturned;
|
jaroslav@1258
|
794 |
}
|
jaroslav@1258
|
795 |
|
jaroslav@1258
|
796 |
public void remove() {
|
jaroslav@1258
|
797 |
if (lastReturned == null)
|
jaroslav@1258
|
798 |
throw new IllegalStateException();
|
jaroslav@1258
|
799 |
if (modCount != expectedModCount)
|
jaroslav@1258
|
800 |
throw new ConcurrentModificationException();
|
jaroslav@1258
|
801 |
|
jaroslav@1258
|
802 |
WeakHashMap.this.remove(currentKey);
|
jaroslav@1258
|
803 |
expectedModCount = modCount;
|
jaroslav@1258
|
804 |
lastReturned = null;
|
jaroslav@1258
|
805 |
currentKey = null;
|
jaroslav@1258
|
806 |
}
|
jaroslav@1258
|
807 |
|
jaroslav@1258
|
808 |
}
|
jaroslav@1258
|
809 |
|
jaroslav@1258
|
810 |
private class ValueIterator extends HashIterator<V> {
|
jaroslav@1258
|
811 |
public V next() {
|
jaroslav@1258
|
812 |
return nextEntry().value;
|
jaroslav@1258
|
813 |
}
|
jaroslav@1258
|
814 |
}
|
jaroslav@1258
|
815 |
|
jaroslav@1258
|
816 |
private class KeyIterator extends HashIterator<K> {
|
jaroslav@1258
|
817 |
public K next() {
|
jaroslav@1258
|
818 |
return nextEntry().getKey();
|
jaroslav@1258
|
819 |
}
|
jaroslav@1258
|
820 |
}
|
jaroslav@1258
|
821 |
|
jaroslav@1258
|
822 |
private class EntryIterator extends HashIterator<Map.Entry<K,V>> {
|
jaroslav@1258
|
823 |
public Map.Entry<K,V> next() {
|
jaroslav@1258
|
824 |
return nextEntry();
|
jaroslav@1258
|
825 |
}
|
jaroslav@1258
|
826 |
}
|
jaroslav@1258
|
827 |
|
jaroslav@1258
|
828 |
// Views
|
jaroslav@1258
|
829 |
|
jaroslav@1258
|
830 |
private transient Set<Map.Entry<K,V>> entrySet = null;
|
jaroslav@1258
|
831 |
|
jaroslav@1258
|
832 |
/**
|
jaroslav@1258
|
833 |
* Returns a {@link Set} view of the keys contained in this map.
|
jaroslav@1258
|
834 |
* The set is backed by the map, so changes to the map are
|
jaroslav@1258
|
835 |
* reflected in the set, and vice-versa. If the map is modified
|
jaroslav@1258
|
836 |
* while an iteration over the set is in progress (except through
|
jaroslav@1258
|
837 |
* the iterator's own <tt>remove</tt> operation), the results of
|
jaroslav@1258
|
838 |
* the iteration are undefined. The set supports element removal,
|
jaroslav@1258
|
839 |
* which removes the corresponding mapping from the map, via the
|
jaroslav@1258
|
840 |
* <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
|
jaroslav@1258
|
841 |
* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
|
jaroslav@1258
|
842 |
* operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
|
jaroslav@1258
|
843 |
* operations.
|
jaroslav@1258
|
844 |
*/
|
jaroslav@1258
|
845 |
public Set<K> keySet() {
|
jaroslav@1258
|
846 |
Set<K> ks = keySet;
|
jaroslav@1258
|
847 |
return (ks != null ? ks : (keySet = new KeySet()));
|
jaroslav@1258
|
848 |
}
|
jaroslav@1258
|
849 |
|
jaroslav@1258
|
850 |
private class KeySet extends AbstractSet<K> {
|
jaroslav@1258
|
851 |
public Iterator<K> iterator() {
|
jaroslav@1258
|
852 |
return new KeyIterator();
|
jaroslav@1258
|
853 |
}
|
jaroslav@1258
|
854 |
|
jaroslav@1258
|
855 |
public int size() {
|
jaroslav@1258
|
856 |
return WeakHashMap.this.size();
|
jaroslav@1258
|
857 |
}
|
jaroslav@1258
|
858 |
|
jaroslav@1258
|
859 |
public boolean contains(Object o) {
|
jaroslav@1258
|
860 |
return containsKey(o);
|
jaroslav@1258
|
861 |
}
|
jaroslav@1258
|
862 |
|
jaroslav@1258
|
863 |
public boolean remove(Object o) {
|
jaroslav@1258
|
864 |
if (containsKey(o)) {
|
jaroslav@1258
|
865 |
WeakHashMap.this.remove(o);
|
jaroslav@1258
|
866 |
return true;
|
jaroslav@1258
|
867 |
}
|
jaroslav@1258
|
868 |
else
|
jaroslav@1258
|
869 |
return false;
|
jaroslav@1258
|
870 |
}
|
jaroslav@1258
|
871 |
|
jaroslav@1258
|
872 |
public void clear() {
|
jaroslav@1258
|
873 |
WeakHashMap.this.clear();
|
jaroslav@1258
|
874 |
}
|
jaroslav@1258
|
875 |
}
|
jaroslav@1258
|
876 |
|
jaroslav@1258
|
877 |
/**
|
jaroslav@1258
|
878 |
* Returns a {@link Collection} view of the values contained in this map.
|
jaroslav@1258
|
879 |
* The collection is backed by the map, so changes to the map are
|
jaroslav@1258
|
880 |
* reflected in the collection, and vice-versa. If the map is
|
jaroslav@1258
|
881 |
* modified while an iteration over the collection is in progress
|
jaroslav@1258
|
882 |
* (except through the iterator's own <tt>remove</tt> operation),
|
jaroslav@1258
|
883 |
* the results of the iteration are undefined. The collection
|
jaroslav@1258
|
884 |
* supports element removal, which removes the corresponding
|
jaroslav@1258
|
885 |
* mapping from the map, via the <tt>Iterator.remove</tt>,
|
jaroslav@1258
|
886 |
* <tt>Collection.remove</tt>, <tt>removeAll</tt>,
|
jaroslav@1258
|
887 |
* <tt>retainAll</tt> and <tt>clear</tt> operations. It does not
|
jaroslav@1258
|
888 |
* support the <tt>add</tt> or <tt>addAll</tt> operations.
|
jaroslav@1258
|
889 |
*/
|
jaroslav@1258
|
890 |
public Collection<V> values() {
|
jaroslav@1258
|
891 |
Collection<V> vs = values;
|
jaroslav@1258
|
892 |
return (vs != null) ? vs : (values = new Values());
|
jaroslav@1258
|
893 |
}
|
jaroslav@1258
|
894 |
|
jaroslav@1258
|
895 |
private class Values extends AbstractCollection<V> {
|
jaroslav@1258
|
896 |
public Iterator<V> iterator() {
|
jaroslav@1258
|
897 |
return new ValueIterator();
|
jaroslav@1258
|
898 |
}
|
jaroslav@1258
|
899 |
|
jaroslav@1258
|
900 |
public int size() {
|
jaroslav@1258
|
901 |
return WeakHashMap.this.size();
|
jaroslav@1258
|
902 |
}
|
jaroslav@1258
|
903 |
|
jaroslav@1258
|
904 |
public boolean contains(Object o) {
|
jaroslav@1258
|
905 |
return containsValue(o);
|
jaroslav@1258
|
906 |
}
|
jaroslav@1258
|
907 |
|
jaroslav@1258
|
908 |
public void clear() {
|
jaroslav@1258
|
909 |
WeakHashMap.this.clear();
|
jaroslav@1258
|
910 |
}
|
jaroslav@1258
|
911 |
}
|
jaroslav@1258
|
912 |
|
jaroslav@1258
|
913 |
/**
|
jaroslav@1258
|
914 |
* Returns a {@link Set} view of the mappings contained in this map.
|
jaroslav@1258
|
915 |
* The set is backed by the map, so changes to the map are
|
jaroslav@1258
|
916 |
* reflected in the set, and vice-versa. If the map is modified
|
jaroslav@1258
|
917 |
* while an iteration over the set is in progress (except through
|
jaroslav@1258
|
918 |
* the iterator's own <tt>remove</tt> operation, or through the
|
jaroslav@1258
|
919 |
* <tt>setValue</tt> operation on a map entry returned by the
|
jaroslav@1258
|
920 |
* iterator) the results of the iteration are undefined. The set
|
jaroslav@1258
|
921 |
* supports element removal, which removes the corresponding
|
jaroslav@1258
|
922 |
* mapping from the map, via the <tt>Iterator.remove</tt>,
|
jaroslav@1258
|
923 |
* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
|
jaroslav@1258
|
924 |
* <tt>clear</tt> operations. It does not support the
|
jaroslav@1258
|
925 |
* <tt>add</tt> or <tt>addAll</tt> operations.
|
jaroslav@1258
|
926 |
*/
|
jaroslav@1258
|
927 |
public Set<Map.Entry<K,V>> entrySet() {
|
jaroslav@1258
|
928 |
Set<Map.Entry<K,V>> es = entrySet;
|
jaroslav@1258
|
929 |
return es != null ? es : (entrySet = new EntrySet());
|
jaroslav@1258
|
930 |
}
|
jaroslav@1258
|
931 |
|
jaroslav@1258
|
932 |
private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
|
jaroslav@1258
|
933 |
public Iterator<Map.Entry<K,V>> iterator() {
|
jaroslav@1258
|
934 |
return new EntryIterator();
|
jaroslav@1258
|
935 |
}
|
jaroslav@1258
|
936 |
|
jaroslav@1258
|
937 |
public boolean contains(Object o) {
|
jaroslav@1258
|
938 |
if (!(o instanceof Map.Entry))
|
jaroslav@1258
|
939 |
return false;
|
jaroslav@1258
|
940 |
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
|
jaroslav@1258
|
941 |
Entry<K,V> candidate = getEntry(e.getKey());
|
jaroslav@1258
|
942 |
return candidate != null && candidate.equals(e);
|
jaroslav@1258
|
943 |
}
|
jaroslav@1258
|
944 |
|
jaroslav@1258
|
945 |
public boolean remove(Object o) {
|
jaroslav@1258
|
946 |
return removeMapping(o);
|
jaroslav@1258
|
947 |
}
|
jaroslav@1258
|
948 |
|
jaroslav@1258
|
949 |
public int size() {
|
jaroslav@1258
|
950 |
return WeakHashMap.this.size();
|
jaroslav@1258
|
951 |
}
|
jaroslav@1258
|
952 |
|
jaroslav@1258
|
953 |
public void clear() {
|
jaroslav@1258
|
954 |
WeakHashMap.this.clear();
|
jaroslav@1258
|
955 |
}
|
jaroslav@1258
|
956 |
|
jaroslav@1258
|
957 |
private List<Map.Entry<K,V>> deepCopy() {
|
jaroslav@1258
|
958 |
List<Map.Entry<K,V>> list = new ArrayList<>(size());
|
jaroslav@1258
|
959 |
for (Map.Entry<K,V> e : this)
|
jaroslav@1258
|
960 |
list.add(new AbstractMap.SimpleEntry<>(e));
|
jaroslav@1258
|
961 |
return list;
|
jaroslav@1258
|
962 |
}
|
jaroslav@1258
|
963 |
|
jaroslav@1258
|
964 |
public Object[] toArray() {
|
jaroslav@1258
|
965 |
return deepCopy().toArray();
|
jaroslav@1258
|
966 |
}
|
jaroslav@1258
|
967 |
|
jaroslav@1258
|
968 |
public <T> T[] toArray(T[] a) {
|
jaroslav@1258
|
969 |
return deepCopy().toArray(a);
|
jaroslav@1258
|
970 |
}
|
jaroslav@1258
|
971 |
}
|
jaroslav@1258
|
972 |
}
|