90 |
|
/* ---------------- Fields -------------- */ |
91 |
|
|
92 |
|
/** |
93 |
< |
* Mask value for indexing into segments. The lower bits of a |
94 |
< |
* key's hash code are used to choose the segment, and the |
95 |
< |
* remaining bits are used as the placement hashcode used within |
96 |
< |
* the segment. |
93 |
> |
* Mask value for indexing into segments. The upper bits of a |
94 |
> |
* key's hash code are used to choose the segment. |
95 |
|
**/ |
96 |
|
private final int segmentMask; |
97 |
|
|
126 |
|
return h; |
127 |
|
} |
128 |
|
|
131 |
– |
/** |
132 |
– |
* Check for equality of non-null references x and y. |
133 |
– |
**/ |
134 |
– |
private static boolean eq(Object x, Object y) { |
135 |
– |
return x == y || x.equals(y); |
136 |
– |
} |
137 |
– |
|
138 |
– |
/** |
139 |
– |
* Return index for hash code h in table of given length. |
140 |
– |
*/ |
141 |
– |
private static int indexFor(int h, int length) { |
142 |
– |
return h & (length-1); |
143 |
– |
} |
144 |
– |
|
129 |
|
/** |
130 |
|
* Return the segment that should be used for key with given hash |
131 |
|
*/ |
132 |
|
private Segment<K,V> segmentFor(int hash) { |
133 |
< |
return segments[hash & segmentMask]; |
150 |
< |
} |
151 |
< |
|
152 |
< |
/** |
153 |
< |
* Strip the segment index from hash code to use as a per-segment hash. |
154 |
< |
*/ |
155 |
< |
private int segmentHashFor(int hash) { |
156 |
< |
return hash >>> segmentShift; |
133 |
> |
return segments[(hash >>> segmentShift) & segmentMask]; |
134 |
|
} |
135 |
|
|
136 |
|
/* ---------------- Inner Classes -------------- */ |
230 |
|
V get(K key, int hash) { |
231 |
|
if (count != 0) { // read-volatile |
232 |
|
HashEntry<K,V>[] tab = table; |
233 |
< |
int index = indexFor(hash, tab.length); |
233 |
> |
int index = hash & (tab.length - 1); |
234 |
|
HashEntry<K,V> e = tab[index]; |
235 |
|
while (e != null) { |
236 |
< |
if (e.hash == hash && eq(key, e.key)) |
236 |
> |
if (e.hash == hash && key.equals(e.key)) |
237 |
|
return e.value; |
238 |
|
e = e.next; |
239 |
|
} |
244 |
|
boolean containsKey(Object key, int hash) { |
245 |
|
if (count != 0) { // read-volatile |
246 |
|
HashEntry<K,V>[] tab = table; |
247 |
< |
int index = indexFor(hash, tab.length); |
247 |
> |
int index = hash & (tab.length - 1); |
248 |
|
HashEntry<K,V> e = tab[index]; |
249 |
|
while (e != null) { |
250 |
< |
if (e.hash == hash && eq(key, e.key)) |
250 |
> |
if (e.hash == hash && key.equals(e.key)) |
251 |
|
return true; |
252 |
|
e = e.next; |
253 |
|
} |
270 |
|
V put(K key, int hash, V value, boolean onlyIfAbsent) { |
271 |
|
lock(); |
272 |
|
try { |
273 |
+ |
int c = count; |
274 |
|
HashEntry<K,V>[] tab = table; |
275 |
< |
int index = indexFor(hash, tab.length); |
275 |
> |
int index = hash & (tab.length - 1); |
276 |
|
HashEntry<K,V> first = tab[index]; |
277 |
|
|
278 |
|
for (HashEntry<K,V> e = first; e != null; e = e.next) { |
279 |
< |
if (e.hash == hash && eq(key, e.key)) { |
279 |
> |
if (e.hash == hash && key.equals(e.key)) { |
280 |
|
V oldValue = e.value; |
281 |
|
if (!onlyIfAbsent) |
282 |
|
e.value = value; |
283 |
< |
count = count; // write-volatile |
283 |
> |
count = c; // write-volatile |
284 |
|
return oldValue; |
285 |
|
} |
286 |
|
} |
287 |
|
|
288 |
|
tab[index] = new HashEntry<K,V>(hash, key, value, first); |
289 |
< |
if (++count > threshold) // write-volatile |
290 |
< |
rehash(); |
289 |
> |
++c; |
290 |
> |
count = c; // write-volatile |
291 |
> |
if (c > threshold) |
292 |
> |
setTable(rehash(tab)); |
293 |
|
return null; |
294 |
|
} |
295 |
|
finally { |
297 |
|
} |
298 |
|
} |
299 |
|
|
300 |
< |
private void rehash() { |
321 |
< |
HashEntry<K,V>[] oldTable = table; |
300 |
> |
private HashEntry<K,V>[] rehash(HashEntry<K,V>[] oldTable) { |
301 |
|
int oldCapacity = oldTable.length; |
302 |
|
if (oldCapacity >= MAXIMUM_CAPACITY) |
303 |
< |
return; |
303 |
> |
return oldTable; |
304 |
|
|
305 |
|
/* |
306 |
|
* Reclassify nodes in each list to new Map. Because we are |
357 |
|
} |
358 |
|
} |
359 |
|
} |
360 |
< |
setTable(newTable); |
360 |
> |
return newTable; |
361 |
|
} |
362 |
|
|
363 |
|
/** |
366 |
|
V remove(Object key, int hash, Object value) { |
367 |
|
lock(); |
368 |
|
try { |
369 |
+ |
int c = count; |
370 |
|
HashEntry[] tab = table; |
371 |
< |
int index = indexFor(hash, tab.length); |
371 |
> |
int index = hash & (tab.length - 1); |
372 |
|
HashEntry<K,V> first = tab[index]; |
373 |
|
|
374 |
|
HashEntry<K,V> e = first; |
375 |
< |
while (true) { |
375 |
> |
for (;;) { |
376 |
|
if (e == null) |
377 |
|
return null; |
378 |
< |
if (e.hash == hash && eq(key, e.key)) |
378 |
> |
if (e.hash == hash && key.equals(e.key)) |
379 |
|
break; |
380 |
|
e = e.next; |
381 |
|
} |
383 |
|
V oldValue = e.value; |
384 |
|
if (value != null && !value.equals(oldValue)) |
385 |
|
return null; |
386 |
< |
|
386 |
> |
|
387 |
|
// All entries following removed node can stay in list, but |
388 |
|
// all preceeding ones need to be cloned. |
389 |
|
HashEntry<K,V> newFirst = e.next; |
391 |
|
newFirst = new HashEntry<K,V>(p.hash, p.key, |
392 |
|
p.value, newFirst); |
393 |
|
tab[index] = newFirst; |
394 |
< |
|
395 |
< |
count--; // write-volatile |
416 |
< |
return e.value; |
394 |
> |
count = c-1; // write-volatile |
395 |
> |
return oldValue; |
396 |
|
} |
397 |
|
finally { |
398 |
|
unlock(); |
491 |
|
++sshift; |
492 |
|
ssize <<= 1; |
493 |
|
} |
494 |
< |
segmentShift = sshift; |
494 |
> |
segmentShift = 32 - sshift; |
495 |
|
segmentMask = ssize - 1; |
496 |
|
this.segments = new Segment<K,V>[ssize]; |
497 |
|
|
570 |
|
*/ |
571 |
|
public V get(K key) { |
572 |
|
int hash = hash(key); // throws NullPointerException if key null |
573 |
< |
return segmentFor(hash).get(key, segmentHashFor(hash)); |
573 |
> |
return segmentFor(hash).get(key, hash); |
574 |
|
} |
575 |
|
|
576 |
|
/** |
586 |
|
*/ |
587 |
|
public boolean containsKey(Object key) { |
588 |
|
int hash = hash(key); // throws NullPointerException if key null |
589 |
< |
return segmentFor(hash).containsKey(key, segmentHashFor(hash)); |
589 |
> |
return segmentFor(hash).containsKey(key, hash); |
590 |
|
} |
591 |
|
|
592 |
|
/** |
653 |
|
if (value == null) |
654 |
|
throw new NullPointerException(); |
655 |
|
int hash = hash(key); |
656 |
< |
return segmentFor(hash).put(key, segmentHashFor(hash), value, false); |
656 |
> |
return segmentFor(hash).put(key, hash, value, false); |
657 |
|
} |
658 |
|
|
659 |
|
/** |
682 |
|
if (value == null) |
683 |
|
throw new NullPointerException(); |
684 |
|
int hash = hash(key); |
685 |
< |
return segmentFor(hash).put(key, segmentHashFor(hash), value, true); |
685 |
> |
return segmentFor(hash).put(key, hash, value, true); |
686 |
|
} |
687 |
|
|
688 |
|
|
714 |
|
*/ |
715 |
|
public V remove(Object key) { |
716 |
|
int hash = hash(key); |
717 |
< |
return segmentFor(hash).remove(key, segmentHashFor(hash), null); |
717 |
> |
return segmentFor(hash).remove(key, hash, null); |
718 |
|
} |
719 |
|
|
720 |
|
/** |
732 |
|
*/ |
733 |
|
public V remove(Object key, Object value) { |
734 |
|
int hash = hash(key); |
735 |
< |
return segmentFor(hash).remove(key, segmentHashFor(hash), value); |
735 |
> |
return segmentFor(hash).remove(key, hash, value); |
736 |
|
} |
737 |
|
|
738 |
|
/** |
1025 |
|
} |
1026 |
|
|
1027 |
|
// Read the keys and values, and put the mappings in the table |
1028 |
< |
while (true) { |
1028 |
> |
for (;;) { |
1029 |
|
K key = (K) s.readObject(); |
1030 |
|
V value = (V) s.readObject(); |
1031 |
|
if (key == null) |