137 |
|
/** |
138 |
|
* The segments, each of which is a specialized hash table |
139 |
|
*/ |
140 |
< |
final Segment[] segments; |
140 |
> |
final Segment<K,V>[] segments; |
141 |
|
|
142 |
|
transient Set<K> keySet; |
143 |
|
transient Set<Map.Entry<K,V>> entrySet; |
166 |
|
* @return the segment |
167 |
|
*/ |
168 |
|
final Segment<K,V> segmentFor(int hash) { |
169 |
< |
return (Segment<K,V>) segments[(hash >>> segmentShift) & segmentMask]; |
169 |
> |
return segments[(hash >>> segmentShift) & segmentMask]; |
170 |
|
} |
171 |
|
|
172 |
|
/* ---------------- Inner Classes -------------- */ |
268 |
|
* The per-segment table. Declared as a raw type, casted |
269 |
|
* to HashEntry<K,V> on each use. |
270 |
|
*/ |
271 |
< |
transient volatile HashEntry[] table; |
271 |
> |
transient volatile HashEntry<K,V>[] table; |
272 |
|
|
273 |
|
/** |
274 |
|
* The load factor for the hash table. Even though this value |
287 |
|
* Sets table to new HashEntry array. |
288 |
|
* Call only while holding lock or in constructor. |
289 |
|
*/ |
290 |
< |
void setTable(HashEntry[] newTable) { |
290 |
> |
void setTable(HashEntry<K,V>[] newTable) { |
291 |
|
threshold = (int)(newTable.length * loadFactor); |
292 |
|
table = newTable; |
293 |
|
} |
296 |
|
* Returns properly casted first entry of bin for given hash. |
297 |
|
*/ |
298 |
|
HashEntry<K,V> getFirst(int hash) { |
299 |
< |
HashEntry[] tab = table; |
300 |
< |
return (HashEntry<K,V>) tab[hash & (tab.length - 1)]; |
299 |
> |
HashEntry<K,V>[] tab = table; |
300 |
> |
return tab[hash & (tab.length - 1)]; |
301 |
|
} |
302 |
|
|
303 |
|
/** |
348 |
|
|
349 |
|
boolean containsValue(Object value) { |
350 |
|
if (count != 0) { // read-volatile |
351 |
< |
HashEntry[] tab = table; |
351 |
> |
HashEntry<K,V>[] tab = table; |
352 |
|
int len = tab.length; |
353 |
|
for (int i = 0 ; i < len; i++) { |
354 |
|
for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i]; |
408 |
|
int c = count; |
409 |
|
if (c++ > threshold) // ensure capacity |
410 |
|
rehash(); |
411 |
< |
HashEntry[] tab = table; |
411 |
> |
HashEntry<K,V>[] tab = table; |
412 |
|
int index = hash & (tab.length - 1); |
413 |
< |
HashEntry<K,V> first = (HashEntry<K,V>) tab[index]; |
413 |
> |
HashEntry<K,V> first = tab[index]; |
414 |
|
HashEntry<K,V> e = first; |
415 |
|
while (e != null && (e.hash != hash || !key.equals(e.key))) |
416 |
|
e = e.next; |
434 |
|
} |
435 |
|
|
436 |
|
void rehash() { |
437 |
< |
HashEntry[] oldTable = table; |
437 |
> |
HashEntry<K,V>[] oldTable = table; |
438 |
|
int oldCapacity = oldTable.length; |
439 |
|
if (oldCapacity >= MAXIMUM_CAPACITY) |
440 |
|
return; |
453 |
|
* right now. |
454 |
|
*/ |
455 |
|
|
456 |
< |
HashEntry[] newTable = new HashEntry[oldCapacity << 1]; |
456 |
> |
HashEntry<K,V>[] newTable = (HashEntry<K,V>[])new HashEntry[oldCapacity << 1]; |
457 |
|
threshold = (int)(newTable.length * loadFactor); |
458 |
|
int sizeMask = newTable.length - 1; |
459 |
|
for (int i = 0; i < oldCapacity ; i++) { |
460 |
|
// We need to guarantee that any existing reads of old Map can |
461 |
|
// proceed. So we cannot yet null out each bin. |
462 |
< |
HashEntry<K,V> e = (HashEntry<K,V>)oldTable[i]; |
462 |
> |
HashEntry<K,V> e = oldTable[i]; |
463 |
|
|
464 |
|
if (e != null) { |
465 |
|
HashEntry<K,V> next = e.next; |
487 |
|
// Clone all remaining nodes |
488 |
|
for (HashEntry<K,V> p = e; p != lastRun; p = p.next) { |
489 |
|
int k = p.hash & sizeMask; |
490 |
< |
HashEntry<K,V> n = (HashEntry<K,V>)newTable[k]; |
490 |
> |
HashEntry<K,V> n = newTable[k]; |
491 |
|
newTable[k] = new HashEntry<K,V>(p.key, p.hash, |
492 |
|
n, p.value); |
493 |
|
} |
504 |
|
lock(); |
505 |
|
try { |
506 |
|
int c = count - 1; |
507 |
< |
HashEntry[] tab = table; |
507 |
> |
HashEntry<K,V>[] tab = table; |
508 |
|
int index = hash & (tab.length - 1); |
509 |
< |
HashEntry<K,V> first = (HashEntry<K,V>)tab[index]; |
509 |
> |
HashEntry<K,V> first = tab[index]; |
510 |
|
HashEntry<K,V> e = first; |
511 |
|
while (e != null && (e.hash != hash || !key.equals(e.key))) |
512 |
|
e = e.next; |
538 |
|
if (count != 0) { |
539 |
|
lock(); |
540 |
|
try { |
541 |
< |
HashEntry[] tab = table; |
541 |
> |
HashEntry<K,V>[] tab = table; |
542 |
|
for (int i = 0; i < tab.length ; i++) |
543 |
|
tab[i] = null; |
544 |
|
++modCount; |
587 |
|
} |
588 |
|
segmentShift = 32 - sshift; |
589 |
|
segmentMask = ssize - 1; |
590 |
< |
this.segments = new Segment[ssize]; |
590 |
> |
this.segments = (Segment<K,V>[]) new Segment[ssize]; |
591 |
|
|
592 |
|
if (initialCapacity > MAXIMUM_CAPACITY) |
593 |
|
initialCapacity = MAXIMUM_CAPACITY; |
665 |
|
* @return <tt>true</tt> if this map contains no key-value mappings |
666 |
|
*/ |
667 |
|
public boolean isEmpty() { |
668 |
< |
final Segment[] segments = this.segments; |
668 |
> |
final Segment<K,V>[] segments = this.segments; |
669 |
|
/* |
670 |
|
* We keep track of per-segment modCounts to avoid ABA |
671 |
|
* problems in which an element in one segment was added and |
704 |
|
* @return the number of key-value mappings in this map |
705 |
|
*/ |
706 |
|
public int size() { |
707 |
< |
final Segment[] segments = this.segments; |
707 |
> |
final Segment<K,V>[] segments = this.segments; |
708 |
|
long sum = 0; |
709 |
|
long check = 0; |
710 |
|
int[] mc = new int[segments.length]; |
790 |
|
|
791 |
|
// See explanation of modCount use above |
792 |
|
|
793 |
< |
final Segment[] segments = this.segments; |
793 |
> |
final Segment<K,V>[] segments = this.segments; |
794 |
|
int[] mc = new int[segments.length]; |
795 |
|
|
796 |
|
// Try a few times without locking |
1050 |
|
abstract class HashIterator { |
1051 |
|
int nextSegmentIndex; |
1052 |
|
int nextTableIndex; |
1053 |
< |
HashEntry[] currentTable; |
1053 |
> |
HashEntry<K,V>[] currentTable; |
1054 |
|
HashEntry<K, V> nextEntry; |
1055 |
|
HashEntry<K, V> lastReturned; |
1056 |
|
|
1067 |
|
return; |
1068 |
|
|
1069 |
|
while (nextTableIndex >= 0) { |
1070 |
< |
if ( (nextEntry = (HashEntry<K,V>)currentTable[nextTableIndex--]) != null) |
1070 |
> |
if ( (nextEntry = currentTable[nextTableIndex--]) != null) |
1071 |
|
return; |
1072 |
|
} |
1073 |
|
|
1074 |
|
while (nextSegmentIndex >= 0) { |
1075 |
< |
Segment<K,V> seg = (Segment<K,V>)segments[nextSegmentIndex--]; |
1075 |
> |
Segment<K,V> seg = segments[nextSegmentIndex--]; |
1076 |
|
if (seg.count != 0) { |
1077 |
|
currentTable = seg.table; |
1078 |
|
for (int j = currentTable.length - 1; j >= 0; --j) { |
1079 |
< |
if ( (nextEntry = (HashEntry<K,V>)currentTable[j]) != null) { |
1079 |
> |
if ( (nextEntry = currentTable[j]) != null) { |
1080 |
|
nextTableIndex = j - 1; |
1081 |
|
return; |
1082 |
|
} |
1151 |
|
return super.equals(o); |
1152 |
|
if (!(o instanceof Map.Entry)) |
1153 |
|
return false; |
1154 |
< |
Map.Entry e = (Map.Entry)o; |
1154 |
> |
Map.Entry<?,?> e = (Map.Entry<?,?>)o; |
1155 |
|
return eq(getKey(), e.getKey()) && eq(getValue(), e.getValue()); |
1156 |
|
} |
1157 |
|
|
1244 |
|
public boolean contains(Object o) { |
1245 |
|
if (!(o instanceof Map.Entry)) |
1246 |
|
return false; |
1247 |
< |
Map.Entry<K,V> e = (Map.Entry<K,V>)o; |
1247 |
> |
Map.Entry<?,?> e = (Map.Entry<?,?>)o; |
1248 |
|
V v = ConcurrentHashMap.this.get(e.getKey()); |
1249 |
|
return v != null && v.equals(e.getValue()); |
1250 |
|
} |
1251 |
|
public boolean remove(Object o) { |
1252 |
|
if (!(o instanceof Map.Entry)) |
1253 |
|
return false; |
1254 |
< |
Map.Entry<K,V> e = (Map.Entry<K,V>)o; |
1254 |
> |
Map.Entry<?,?> e = (Map.Entry<?,?>)o; |
1255 |
|
return ConcurrentHashMap.this.remove(e.getKey(), e.getValue()); |
1256 |
|
} |
1257 |
|
public int size() { |
1292 |
|
s.defaultWriteObject(); |
1293 |
|
|
1294 |
|
for (int k = 0; k < segments.length; ++k) { |
1295 |
< |
Segment<K,V> seg = (Segment<K,V>)segments[k]; |
1295 |
> |
Segment<K,V> seg = segments[k]; |
1296 |
|
seg.lock(); |
1297 |
|
try { |
1298 |
< |
HashEntry[] tab = seg.table; |
1298 |
> |
HashEntry<K,V>[] tab = seg.table; |
1299 |
|
for (int i = 0; i < tab.length; ++i) { |
1300 |
< |
for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i]; e != null; e = e.next) { |
1300 |
> |
for (HashEntry<K,V> e = tab[i]; e != null; e = e.next) { |
1301 |
|
s.writeObject(e.key); |
1302 |
|
s.writeObject(e.value); |
1303 |
|
} |