20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 * or visit www.oracle.com if you need additional information or have any
22 * questions.
23 */
24
25 /*
26 * This file is available under and governed by the GNU General Public
27 * License version 2 only, as published by the Free Software Foundation.
28 * However, the following notice accompanied the original version of this
29 * file:
30 *
31 * Written by Doug Lea with assistance from members of JCP JSR-166
32 * Expert Group and released to the public domain, as explained at
33 * http://creativecommons.org/publicdomain/zero/1.0/
34 */
35
36 package java.util.concurrent;
37 import java.util.concurrent.locks.*;
38 import java.util.*;
39 import java.io.Serializable;
40 import java.io.IOException;
41 import java.io.ObjectInputStream;
42 import java.io.ObjectOutputStream;
43
44 /**
45 * A hash table supporting full concurrency of retrievals and
46 * adjustable expected concurrency for updates. This class obeys the
47 * same functional specification as {@link java.util.Hashtable}, and
48 * includes versions of methods corresponding to each method of
49 * <tt>Hashtable</tt>. However, even though all operations are
50 * thread-safe, retrieval operations do <em>not</em> entail locking,
51 * and there is <em>not</em> any support for locking the entire table
52 * in a way that prevents all access. This class is fully
53 * interoperable with <tt>Hashtable</tt> in programs that rely on its
54 * thread safety but not on its synchronization details.
55 *
56 * <p> Retrieval operations (including <tt>get</tt>) generally do not
57 * block, so may overlap with update operations (including
58 * <tt>put</tt> and <tt>remove</tt>). Retrievals reflect the results
59 * of the most recently <em>completed</em> update operations holding
60 * upon their onset. For aggregate operations such as <tt>putAll</tt>
61 * and <tt>clear</tt>, concurrent retrievals may reflect insertion or
62 * removal of only some entries. Similarly, Iterators and
211 this.hash = hash;
212 this.key = key;
213 this.value = value;
214 this.next = next;
215 }
216
217 /**
218 * Sets next field with volatile write semantics. (See above
219 * about use of putOrderedObject.)
220 */
221 final void setNext(HashEntry<K,V> n) {
222 UNSAFE.putOrderedObject(this, nextOffset, n);
223 }
224
225 // Unsafe mechanics
226 static final sun.misc.Unsafe UNSAFE;
227 static final long nextOffset;
228 static {
229 try {
230 UNSAFE = sun.misc.Unsafe.getUnsafe();
231 Class k = HashEntry.class;
232 nextOffset = UNSAFE.objectFieldOffset
233 (k.getDeclaredField("next"));
234 } catch (Exception e) {
235 throw new Error(e);
236 }
237 }
238 }
239
240 /**
241 * Gets the ith element of given table (if nonnull) with volatile
242 * read semantics. Note: This is manually integrated into a few
243 * performance-sensitive methods to reduce call overhead.
244 */
245 @SuppressWarnings("unchecked")
246 static final <K,V> HashEntry<K,V> entryAt(HashEntry<K,V>[] tab, int i) {
247 return (tab == null) ? null :
248 (HashEntry<K,V>) UNSAFE.getObjectVolatile
249 (tab, ((long)i << TSHIFT) + TBASE);
250 }
251
416 * Reclassify nodes in each list to new table. Because we
417 * are using power-of-two expansion, the elements from
418 * each bin must either stay at same index, or move with a
419 * power of two offset. We eliminate unnecessary node
420 * creation by catching cases where old nodes can be
421 * reused because their next fields won't change.
422 * Statistically, at the default threshold, only about
423 * one-sixth of them need cloning when a table
424 * doubles. The nodes they replace will be garbage
425 * collectable as soon as they are no longer referenced by
426 * any reader thread that may be in the midst of
427 * concurrently traversing table. Entry accesses use plain
428 * array indexing because they are followed by volatile
429 * table write.
430 */
431 HashEntry<K,V>[] oldTable = table;
432 int oldCapacity = oldTable.length;
433 int newCapacity = oldCapacity << 1;
434 threshold = (int)(newCapacity * loadFactor);
435 HashEntry<K,V>[] newTable =
436 (HashEntry<K,V>[]) new HashEntry[newCapacity];
437 int sizeMask = newCapacity - 1;
438 for (int i = 0; i < oldCapacity ; i++) {
439 HashEntry<K,V> e = oldTable[i];
440 if (e != null) {
441 HashEntry<K,V> next = e.next;
442 int idx = e.hash & sizeMask;
443 if (next == null) // Single node on list
444 newTable[idx] = e;
445 else { // Reuse consecutive sequence at same slot
446 HashEntry<K,V> lastRun = e;
447 int lastIdx = idx;
448 for (HashEntry<K,V> last = next;
449 last != null;
450 last = last.next) {
451 int k = last.hash & sizeMask;
452 if (k != lastIdx) {
453 lastIdx = k;
454 lastRun = last;
455 }
456 }
660 (Segment<K,V>) UNSAFE.getObjectVolatile(ss, u);
661 }
662
663 /**
664 * Returns the segment for the given index, creating it and
665 * recording in segment table (via CAS) if not already present.
666 *
667 * @param k the index
668 * @return the segment
669 */
670 @SuppressWarnings("unchecked")
671 private Segment<K,V> ensureSegment(int k) {
672 final Segment<K,V>[] ss = this.segments;
673 long u = (k << SSHIFT) + SBASE; // raw offset
674 Segment<K,V> seg;
675 if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
676 Segment<K,V> proto = ss[0]; // use segment 0 as prototype
677 int cap = proto.table.length;
678 float lf = proto.loadFactor;
679 int threshold = (int)(cap * lf);
680 HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
681 if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
682 == null) { // recheck
683 Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
684 while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
685 == null) {
686 if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
687 break;
688 }
689 }
690 }
691 return seg;
692 }
693
694 // Hash-based segment and entry accesses
695
696 /**
697 * Get the segment for the given hash
698 */
699 @SuppressWarnings("unchecked")
700 private Segment<K,V> segmentForHash(int h) {
701 long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
702 return (Segment<K,V>) UNSAFE.getObjectVolatile(segments, u);
703 }
704
705 /**
706 * Gets the table entry for the given segment and hash
707 */
708 @SuppressWarnings("unchecked")
709 static final <K,V> HashEntry<K,V> entryForHash(Segment<K,V> seg, int h) {
710 HashEntry<K,V>[] tab;
711 return (seg == null || (tab = seg.table) == null) ? null :
712 (HashEntry<K,V>) UNSAFE.getObjectVolatile
713 (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
714 }
715
716 /* ---------------- Public operations -------------- */
717
718 /**
719 * Creates a new, empty map with the specified initial
720 * capacity, load factor and concurrency level.
721 *
722 * @param initialCapacity the initial capacity. The implementation
723 * performs internal sizing to accommodate this many elements.
724 * @param loadFactor the load factor threshold, used to control resizing.
725 * Resizing may be performed when the average number of elements per
726 * bin exceeds this threshold.
741 // Find power-of-two sizes best matching arguments
742 int sshift = 0;
743 int ssize = 1;
744 while (ssize < concurrencyLevel) {
745 ++sshift;
746 ssize <<= 1;
747 }
748 this.segmentShift = 32 - sshift;
749 this.segmentMask = ssize - 1;
750 if (initialCapacity > MAXIMUM_CAPACITY)
751 initialCapacity = MAXIMUM_CAPACITY;
752 int c = initialCapacity / ssize;
753 if (c * ssize < initialCapacity)
754 ++c;
755 int cap = MIN_SEGMENT_TABLE_CAPACITY;
756 while (cap < c)
757 cap <<= 1;
758 // create segments and segments[0]
759 Segment<K,V> s0 =
760 new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
761 (HashEntry<K,V>[])new HashEntry[cap]);
762 Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
763 UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
764 this.segments = ss;
765 }
766
767 /**
768 * Creates a new, empty map with the specified initial capacity
769 * and load factor and with the default concurrencyLevel (16).
770 *
771 * @param initialCapacity The implementation performs internal
772 * sizing to accommodate this many elements.
773 * @param loadFactor the load factor threshold, used to control resizing.
774 * Resizing may be performed when the average number of elements per
775 * bin exceeds this threshold.
776 * @throws IllegalArgumentException if the initial capacity of
777 * elements is negative or the load factor is nonpositive
778 *
779 * @since 1.6
780 */
781 public ConcurrentHashMap(int initialCapacity, float loadFactor) {
782 this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
899 } finally {
900 if (retries > RETRIES_BEFORE_LOCK) {
901 for (int j = 0; j < segments.length; ++j)
902 segmentAt(segments, j).unlock();
903 }
904 }
905 return overflow ? Integer.MAX_VALUE : size;
906 }
907
908 /**
909 * Returns the value to which the specified key is mapped,
910 * or {@code null} if this map contains no mapping for the key.
911 *
912 * <p>More formally, if this map contains a mapping from a key
913 * {@code k} to a value {@code v} such that {@code key.equals(k)},
914 * then this method returns {@code v}; otherwise it returns
915 * {@code null}. (There can be at most one such mapping.)
916 *
917 * @throws NullPointerException if the specified key is null
918 */
919 public V get(Object key) {
920 Segment<K,V> s; // manually integrate access methods to reduce overhead
921 HashEntry<K,V>[] tab;
922 int h = hash(key.hashCode());
923 long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
924 if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
925 (tab = s.table) != null) {
926 for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
927 (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
928 e != null; e = e.next) {
929 K k;
930 if ((k = e.key) == key || (e.hash == h && key.equals(k)))
931 return e.value;
932 }
933 }
934 return null;
935 }
936
937 /**
938 * Tests if the specified object is a key in this table.
1009 if (retries > 0 && sum == last)
1010 break;
1011 last = sum;
1012 }
1013 } finally {
1014 if (retries > RETRIES_BEFORE_LOCK) {
1015 for (int j = 0; j < segments.length; ++j)
1016 segmentAt(segments, j).unlock();
1017 }
1018 }
1019 return found;
1020 }
1021
1022 /**
1023 * Legacy method testing if some key maps into the specified value
1024 * in this table. This method is identical in functionality to
1025 * {@link #containsValue}, and exists solely to ensure
1026 * full compatibility with class {@link java.util.Hashtable},
1027 * which supported this method prior to introduction of the
1028 * Java Collections framework.
1029
1030 * @param value a value to search for
1031 * @return <tt>true</tt> if and only if some key maps to the
1032 * <tt>value</tt> argument in this table as
1033 * determined by the <tt>equals</tt> method;
1034 * <tt>false</tt> otherwise
1035 * @throws NullPointerException if the specified value is null
1036 */
1037 public boolean contains(Object value) {
1038 return containsValue(value);
1039 }
1040
1041 /**
1042 * Maps the specified key to the specified value in this table.
1043 * Neither the key nor the value can be null.
1044 *
1045 * <p> The value can be retrieved by calling the <tt>get</tt> method
1046 * with a key that is equal to the original key.
1047 *
1048 * @param key key with which the specified value is to be associated
1049 * @param value value to be associated with the specified key
1245 public Enumeration<V> elements() {
1246 return new ValueIterator();
1247 }
1248
1249 /* ---------------- Iterator Support -------------- */
1250
1251 abstract class HashIterator {
1252 int nextSegmentIndex;
1253 int nextTableIndex;
1254 HashEntry<K,V>[] currentTable;
1255 HashEntry<K, V> nextEntry;
1256 HashEntry<K, V> lastReturned;
1257
1258 HashIterator() {
1259 nextSegmentIndex = segments.length - 1;
1260 nextTableIndex = -1;
1261 advance();
1262 }
1263
1264 /**
1265 * Set nextEntry to first node of next non-empty table
1266 * (in backwards order, to simplify checks).
1267 */
1268 final void advance() {
1269 for (;;) {
1270 if (nextTableIndex >= 0) {
1271 if ((nextEntry = entryAt(currentTable,
1272 nextTableIndex--)) != null)
1273 break;
1274 }
1275 else if (nextSegmentIndex >= 0) {
1276 Segment<K,V> seg = segmentAt(segments, nextSegmentIndex--);
1277 if (seg != null && (currentTable = seg.table) != null)
1278 nextTableIndex = currentTable.length - 1;
1279 }
1280 else
1281 break;
1282 }
1283 }
1284
1285 final HashEntry<K,V> nextEntry() {
1309 {
1310 public final K next() { return super.nextEntry().key; }
1311 public final K nextElement() { return super.nextEntry().key; }
1312 }
1313
1314 final class ValueIterator
1315 extends HashIterator
1316 implements Iterator<V>, Enumeration<V>
1317 {
1318 public final V next() { return super.nextEntry().value; }
1319 public final V nextElement() { return super.nextEntry().value; }
1320 }
1321
1322 /**
1323 * Custom Entry class used by EntryIterator.next(), that relays
1324 * setValue changes to the underlying map.
1325 */
1326 final class WriteThroughEntry
1327 extends AbstractMap.SimpleEntry<K,V>
1328 {
1329 WriteThroughEntry(K k, V v) {
1330 super(k,v);
1331 }
1332
1333 /**
1334 * Set our entry's value and write through to the map. The
1335 * value to return is somewhat arbitrary here. Since a
1336 * WriteThroughEntry does not necessarily track asynchronous
1337 * changes, the most recent "previous" value could be
1338 * different from what we return (or could even have been
1339 * removed in which case the put will re-establish). We do not
1340 * and cannot guarantee more.
1341 */
1342 public V setValue(V value) {
1343 if (value == null) throw new NullPointerException();
1344 V v = super.setValue(value);
1345 ConcurrentHashMap.this.put(getKey(), value);
1346 return v;
1347 }
1348 }
1349
1350 final class EntryIterator
1351 extends HashIterator
1352 implements Iterator<Entry<K,V>>
1353 {
1354 public Map.Entry<K,V> next() {
1410 public boolean remove(Object o) {
1411 if (!(o instanceof Map.Entry))
1412 return false;
1413 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1414 return ConcurrentHashMap.this.remove(e.getKey(), e.getValue());
1415 }
1416 public int size() {
1417 return ConcurrentHashMap.this.size();
1418 }
1419 public boolean isEmpty() {
1420 return ConcurrentHashMap.this.isEmpty();
1421 }
1422 public void clear() {
1423 ConcurrentHashMap.this.clear();
1424 }
1425 }
1426
1427 /* ---------------- Serialization Support -------------- */
1428
1429 /**
1430 * Save the state of the <tt>ConcurrentHashMap</tt> instance to a
1431 * stream (i.e., serialize it).
1432 * @param s the stream
1433 * @serialData
1434 * the key (Object) and value (Object)
1435 * for each key-value mapping, followed by a null pair.
1436 * The key-value mappings are emitted in no particular order.
1437 */
1438 private void writeObject(java.io.ObjectOutputStream s) throws IOException {
1439 // force all segments for serialization compatibility
1440 for (int k = 0; k < segments.length; ++k)
1441 ensureSegment(k);
1442 s.defaultWriteObject();
1443
1444 final Segment<K,V>[] segments = this.segments;
1445 for (int k = 0; k < segments.length; ++k) {
1446 Segment<K,V> seg = segmentAt(segments, k);
1447 seg.lock();
1448 try {
1449 HashEntry<K,V>[] tab = seg.table;
1450 for (int i = 0; i < tab.length; ++i) {
1451 HashEntry<K,V> e;
1452 for (e = entryAt(tab, i); e != null; e = e.next) {
1453 s.writeObject(e.key);
1454 s.writeObject(e.value);
1455 }
1456 }
1457 } finally {
1458 seg.unlock();
1459 }
1460 }
1461 s.writeObject(null);
1462 s.writeObject(null);
1463 }
1464
1465 /**
1466 * Reconstitute the <tt>ConcurrentHashMap</tt> instance from a
1467 * stream (i.e., deserialize it).
1468 * @param s the stream
1469 */
1470 @SuppressWarnings("unchecked")
1471 private void readObject(java.io.ObjectInputStream s)
1472 throws IOException, ClassNotFoundException {
1473 s.defaultReadObject();
1474
1475 // Re-initialize segments to be minimally sized, and let grow.
1476 int cap = MIN_SEGMENT_TABLE_CAPACITY;
1477 final Segment<K,V>[] segments = this.segments;
1478 for (int k = 0; k < segments.length; ++k) {
1479 Segment<K,V> seg = segments[k];
1480 if (seg != null) {
1481 seg.threshold = (int)(cap * seg.loadFactor);
1482 seg.table = (HashEntry<K,V>[]) new HashEntry[cap];
1483 }
1484 }
1485
1486 // Read the keys and values, and put the mappings in the table
1487 for (;;) {
1488 K key = (K) s.readObject();
1489 V value = (V) s.readObject();
1490 if (key == null)
1491 break;
1492 put(key, value);
1493 }
1494 }
1495
1496 // Unsafe mechanics
1497 private static final sun.misc.Unsafe UNSAFE;
1498 private static final long SBASE;
1499 private static final int SSHIFT;
1500 private static final long TBASE;
1501 private static final int TSHIFT;
1502
1503 static {
1504 int ss, ts;
1505 try {
1506 UNSAFE = sun.misc.Unsafe.getUnsafe();
1507 Class tc = HashEntry[].class;
1508 Class sc = Segment[].class;
1509 TBASE = UNSAFE.arrayBaseOffset(tc);
1510 SBASE = UNSAFE.arrayBaseOffset(sc);
1511 ts = UNSAFE.arrayIndexScale(tc);
1512 ss = UNSAFE.arrayIndexScale(sc);
1513 } catch (Exception e) {
1514 throw new Error(e);
1515 }
1516 if ((ss & (ss-1)) != 0 || (ts & (ts-1)) != 0)
1517 throw new Error("data type scale not a power of two");
1518 SSHIFT = 31 - Integer.numberOfLeadingZeros(ss);
1519 TSHIFT = 31 - Integer.numberOfLeadingZeros(ts);
1520 }
1521
1522 }
|
20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 * or visit www.oracle.com if you need additional information or have any
22 * questions.
23 */
24
25 /*
26 * This file is available under and governed by the GNU General Public
27 * License version 2 only, as published by the Free Software Foundation.
28 * However, the following notice accompanied the original version of this
29 * file:
30 *
31 * Written by Doug Lea with assistance from members of JCP JSR-166
32 * Expert Group and released to the public domain, as explained at
33 * http://creativecommons.org/publicdomain/zero/1.0/
34 */
35
36 package java.util.concurrent;
37 import java.util.concurrent.locks.*;
38 import java.util.*;
39 import java.io.Serializable;
40
41 /**
42 * A hash table supporting full concurrency of retrievals and
43 * adjustable expected concurrency for updates. This class obeys the
44 * same functional specification as {@link java.util.Hashtable}, and
45 * includes versions of methods corresponding to each method of
46 * <tt>Hashtable</tt>. However, even though all operations are
47 * thread-safe, retrieval operations do <em>not</em> entail locking,
48 * and there is <em>not</em> any support for locking the entire table
49 * in a way that prevents all access. This class is fully
50 * interoperable with <tt>Hashtable</tt> in programs that rely on its
51 * thread safety but not on its synchronization details.
52 *
53 * <p> Retrieval operations (including <tt>get</tt>) generally do not
54 * block, so may overlap with update operations (including
55 * <tt>put</tt> and <tt>remove</tt>). Retrievals reflect the results
56 * of the most recently <em>completed</em> update operations holding
57 * upon their onset. For aggregate operations such as <tt>putAll</tt>
58 * and <tt>clear</tt>, concurrent retrievals may reflect insertion or
59 * removal of only some entries. Similarly, Iterators and
208 this.hash = hash;
209 this.key = key;
210 this.value = value;
211 this.next = next;
212 }
213
214 /**
215 * Sets next field with volatile write semantics. (See above
216 * about use of putOrderedObject.)
217 */
218 final void setNext(HashEntry<K,V> n) {
219 UNSAFE.putOrderedObject(this, nextOffset, n);
220 }
221
222 // Unsafe mechanics
223 static final sun.misc.Unsafe UNSAFE;
224 static final long nextOffset;
225 static {
226 try {
227 UNSAFE = sun.misc.Unsafe.getUnsafe();
228 Class<?> k = HashEntry.class;
229 nextOffset = UNSAFE.objectFieldOffset
230 (k.getDeclaredField("next"));
231 } catch (Exception e) {
232 throw new Error(e);
233 }
234 }
235 }
236
237 /**
238 * Gets the ith element of given table (if nonnull) with volatile
239 * read semantics. Note: This is manually integrated into a few
240 * performance-sensitive methods to reduce call overhead.
241 */
242 @SuppressWarnings("unchecked")
243 static final <K,V> HashEntry<K,V> entryAt(HashEntry<K,V>[] tab, int i) {
244 return (tab == null) ? null :
245 (HashEntry<K,V>) UNSAFE.getObjectVolatile
246 (tab, ((long)i << TSHIFT) + TBASE);
247 }
248
413 * Reclassify nodes in each list to new table. Because we
414 * are using power-of-two expansion, the elements from
415 * each bin must either stay at same index, or move with a
416 * power of two offset. We eliminate unnecessary node
417 * creation by catching cases where old nodes can be
418 * reused because their next fields won't change.
419 * Statistically, at the default threshold, only about
420 * one-sixth of them need cloning when a table
421 * doubles. The nodes they replace will be garbage
422 * collectable as soon as they are no longer referenced by
423 * any reader thread that may be in the midst of
424 * concurrently traversing table. Entry accesses use plain
425 * array indexing because they are followed by volatile
426 * table write.
427 */
428 HashEntry<K,V>[] oldTable = table;
429 int oldCapacity = oldTable.length;
430 int newCapacity = oldCapacity << 1;
431 threshold = (int)(newCapacity * loadFactor);
432 HashEntry<K,V>[] newTable =
433 (HashEntry<K,V>[]) new HashEntry<?,?>[newCapacity];
434 int sizeMask = newCapacity - 1;
435 for (int i = 0; i < oldCapacity ; i++) {
436 HashEntry<K,V> e = oldTable[i];
437 if (e != null) {
438 HashEntry<K,V> next = e.next;
439 int idx = e.hash & sizeMask;
440 if (next == null) // Single node on list
441 newTable[idx] = e;
442 else { // Reuse consecutive sequence at same slot
443 HashEntry<K,V> lastRun = e;
444 int lastIdx = idx;
445 for (HashEntry<K,V> last = next;
446 last != null;
447 last = last.next) {
448 int k = last.hash & sizeMask;
449 if (k != lastIdx) {
450 lastIdx = k;
451 lastRun = last;
452 }
453 }
657 (Segment<K,V>) UNSAFE.getObjectVolatile(ss, u);
658 }
659
660 /**
661 * Returns the segment for the given index, creating it and
662 * recording in segment table (via CAS) if not already present.
663 *
664 * @param k the index
665 * @return the segment
666 */
667 @SuppressWarnings("unchecked")
668 private Segment<K,V> ensureSegment(int k) {
669 final Segment<K,V>[] ss = this.segments;
670 long u = (k << SSHIFT) + SBASE; // raw offset
671 Segment<K,V> seg;
672 if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
673 Segment<K,V> proto = ss[0]; // use segment 0 as prototype
674 int cap = proto.table.length;
675 float lf = proto.loadFactor;
676 int threshold = (int)(cap * lf);
677 HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry<?,?>[cap];
678 if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
679 == null) { // recheck
680 Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
681 while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
682 == null) {
683 if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
684 break;
685 }
686 }
687 }
688 return seg;
689 }
690
691 // Hash-based segment and entry accesses
692
693 /**
694 * Gets the segment for the given hash code.
695 */
696 @SuppressWarnings("unchecked")
697 private Segment<K,V> segmentForHash(int h) {
698 long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
699 return (Segment<K,V>) UNSAFE.getObjectVolatile(segments, u);
700 }
701
702 /**
703 * Gets the table entry for the given segment and hash code.
704 */
705 @SuppressWarnings("unchecked")
706 static final <K,V> HashEntry<K,V> entryForHash(Segment<K,V> seg, int h) {
707 HashEntry<K,V>[] tab;
708 return (seg == null || (tab = seg.table) == null) ? null :
709 (HashEntry<K,V>) UNSAFE.getObjectVolatile
710 (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
711 }
712
713 /* ---------------- Public operations -------------- */
714
715 /**
716 * Creates a new, empty map with the specified initial
717 * capacity, load factor and concurrency level.
718 *
719 * @param initialCapacity the initial capacity. The implementation
720 * performs internal sizing to accommodate this many elements.
721 * @param loadFactor the load factor threshold, used to control resizing.
722 * Resizing may be performed when the average number of elements per
723 * bin exceeds this threshold.
738 // Find power-of-two sizes best matching arguments
739 int sshift = 0;
740 int ssize = 1;
741 while (ssize < concurrencyLevel) {
742 ++sshift;
743 ssize <<= 1;
744 }
745 this.segmentShift = 32 - sshift;
746 this.segmentMask = ssize - 1;
747 if (initialCapacity > MAXIMUM_CAPACITY)
748 initialCapacity = MAXIMUM_CAPACITY;
749 int c = initialCapacity / ssize;
750 if (c * ssize < initialCapacity)
751 ++c;
752 int cap = MIN_SEGMENT_TABLE_CAPACITY;
753 while (cap < c)
754 cap <<= 1;
755 // create segments and segments[0]
756 Segment<K,V> s0 =
757 new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
758 (HashEntry<K,V>[])new HashEntry<?,?>[cap]);
759 Segment<K,V>[] ss = (Segment<K,V>[])new Segment<?,?>[ssize];
760 UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
761 this.segments = ss;
762 }
763
764 /**
765 * Creates a new, empty map with the specified initial capacity
766 * and load factor and with the default concurrencyLevel (16).
767 *
768 * @param initialCapacity The implementation performs internal
769 * sizing to accommodate this many elements.
770 * @param loadFactor the load factor threshold, used to control resizing.
771 * Resizing may be performed when the average number of elements per
772 * bin exceeds this threshold.
773 * @throws IllegalArgumentException if the initial capacity of
774 * elements is negative or the load factor is nonpositive
775 *
776 * @since 1.6
777 */
778 public ConcurrentHashMap(int initialCapacity, float loadFactor) {
779 this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
896 } finally {
897 if (retries > RETRIES_BEFORE_LOCK) {
898 for (int j = 0; j < segments.length; ++j)
899 segmentAt(segments, j).unlock();
900 }
901 }
902 return overflow ? Integer.MAX_VALUE : size;
903 }
904
905 /**
906 * Returns the value to which the specified key is mapped,
907 * or {@code null} if this map contains no mapping for the key.
908 *
909 * <p>More formally, if this map contains a mapping from a key
910 * {@code k} to a value {@code v} such that {@code key.equals(k)},
911 * then this method returns {@code v}; otherwise it returns
912 * {@code null}. (There can be at most one such mapping.)
913 *
914 * @throws NullPointerException if the specified key is null
915 */
916 @SuppressWarnings("unchecked")
917 public V get(Object key) {
918 Segment<K,V> s; // manually integrate access methods to reduce overhead
919 HashEntry<K,V>[] tab;
920 int h = hash(key.hashCode());
921 long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
922 if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
923 (tab = s.table) != null) {
924 for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
925 (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
926 e != null; e = e.next) {
927 K k;
928 if ((k = e.key) == key || (e.hash == h && key.equals(k)))
929 return e.value;
930 }
931 }
932 return null;
933 }
934
935 /**
936 * Tests if the specified object is a key in this table.
1007 if (retries > 0 && sum == last)
1008 break;
1009 last = sum;
1010 }
1011 } finally {
1012 if (retries > RETRIES_BEFORE_LOCK) {
1013 for (int j = 0; j < segments.length; ++j)
1014 segmentAt(segments, j).unlock();
1015 }
1016 }
1017 return found;
1018 }
1019
1020 /**
1021 * Legacy method testing if some key maps into the specified value
1022 * in this table. This method is identical in functionality to
1023 * {@link #containsValue}, and exists solely to ensure
1024 * full compatibility with class {@link java.util.Hashtable},
1025 * which supported this method prior to introduction of the
1026 * Java Collections framework.
1027 *
1028 * @param value a value to search for
1029 * @return <tt>true</tt> if and only if some key maps to the
1030 * <tt>value</tt> argument in this table as
1031 * determined by the <tt>equals</tt> method;
1032 * <tt>false</tt> otherwise
1033 * @throws NullPointerException if the specified value is null
1034 */
1035 public boolean contains(Object value) {
1036 return containsValue(value);
1037 }
1038
1039 /**
1040 * Maps the specified key to the specified value in this table.
1041 * Neither the key nor the value can be null.
1042 *
1043 * <p> The value can be retrieved by calling the <tt>get</tt> method
1044 * with a key that is equal to the original key.
1045 *
1046 * @param key key with which the specified value is to be associated
1047 * @param value value to be associated with the specified key
1243 public Enumeration<V> elements() {
1244 return new ValueIterator();
1245 }
1246
1247 /* ---------------- Iterator Support -------------- */
1248
1249 abstract class HashIterator {
1250 int nextSegmentIndex;
1251 int nextTableIndex;
1252 HashEntry<K,V>[] currentTable;
1253 HashEntry<K, V> nextEntry;
1254 HashEntry<K, V> lastReturned;
1255
1256 HashIterator() {
1257 nextSegmentIndex = segments.length - 1;
1258 nextTableIndex = -1;
1259 advance();
1260 }
1261
1262 /**
1263 * Sets nextEntry to first node of next non-empty table
1264 * (in backwards order, to simplify checks).
1265 */
1266 final void advance() {
1267 for (;;) {
1268 if (nextTableIndex >= 0) {
1269 if ((nextEntry = entryAt(currentTable,
1270 nextTableIndex--)) != null)
1271 break;
1272 }
1273 else if (nextSegmentIndex >= 0) {
1274 Segment<K,V> seg = segmentAt(segments, nextSegmentIndex--);
1275 if (seg != null && (currentTable = seg.table) != null)
1276 nextTableIndex = currentTable.length - 1;
1277 }
1278 else
1279 break;
1280 }
1281 }
1282
1283 final HashEntry<K,V> nextEntry() {
1307 {
1308 public final K next() { return super.nextEntry().key; }
1309 public final K nextElement() { return super.nextEntry().key; }
1310 }
1311
1312 final class ValueIterator
1313 extends HashIterator
1314 implements Iterator<V>, Enumeration<V>
1315 {
1316 public final V next() { return super.nextEntry().value; }
1317 public final V nextElement() { return super.nextEntry().value; }
1318 }
1319
1320 /**
1321 * Custom Entry class used by EntryIterator.next(), that relays
1322 * setValue changes to the underlying map.
1323 */
1324 final class WriteThroughEntry
1325 extends AbstractMap.SimpleEntry<K,V>
1326 {
1327 static final long serialVersionUID = 7249069246763182397L;
1328
1329 WriteThroughEntry(K k, V v) {
1330 super(k,v);
1331 }
1332
1333 /**
1334 * Sets our entry's value and writes through to the map. The
1335 * value to return is somewhat arbitrary here. Since a
1336 * WriteThroughEntry does not necessarily track asynchronous
1337 * changes, the most recent "previous" value could be
1338 * different from what we return (or could even have been
1339 * removed in which case the put will re-establish). We do not
1340 * and cannot guarantee more.
1341 */
1342 public V setValue(V value) {
1343 if (value == null) throw new NullPointerException();
1344 V v = super.setValue(value);
1345 ConcurrentHashMap.this.put(getKey(), value);
1346 return v;
1347 }
1348 }
1349
1350 final class EntryIterator
1351 extends HashIterator
1352 implements Iterator<Entry<K,V>>
1353 {
1354 public Map.Entry<K,V> next() {
1410 public boolean remove(Object o) {
1411 if (!(o instanceof Map.Entry))
1412 return false;
1413 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1414 return ConcurrentHashMap.this.remove(e.getKey(), e.getValue());
1415 }
1416 public int size() {
1417 return ConcurrentHashMap.this.size();
1418 }
1419 public boolean isEmpty() {
1420 return ConcurrentHashMap.this.isEmpty();
1421 }
1422 public void clear() {
1423 ConcurrentHashMap.this.clear();
1424 }
1425 }
1426
1427 /* ---------------- Serialization Support -------------- */
1428
1429 /**
1430 * Saves the state of the <tt>ConcurrentHashMap</tt> instance to a
1431 * stream (i.e., serializes it).
1432 * @param s the stream
1433 * @serialData
1434 * the key (Object) and value (Object)
1435 * for each key-value mapping, followed by a null pair.
1436 * The key-value mappings are emitted in no particular order.
1437 */
1438 private void writeObject(java.io.ObjectOutputStream s)
1439 throws java.io.IOException {
1440 // force all segments for serialization compatibility
1441 for (int k = 0; k < segments.length; ++k)
1442 ensureSegment(k);
1443 s.defaultWriteObject();
1444
1445 final Segment<K,V>[] segments = this.segments;
1446 for (int k = 0; k < segments.length; ++k) {
1447 Segment<K,V> seg = segmentAt(segments, k);
1448 seg.lock();
1449 try {
1450 HashEntry<K,V>[] tab = seg.table;
1451 for (int i = 0; i < tab.length; ++i) {
1452 HashEntry<K,V> e;
1453 for (e = entryAt(tab, i); e != null; e = e.next) {
1454 s.writeObject(e.key);
1455 s.writeObject(e.value);
1456 }
1457 }
1458 } finally {
1459 seg.unlock();
1460 }
1461 }
1462 s.writeObject(null);
1463 s.writeObject(null);
1464 }
1465
1466 /**
1467 * Reconstitutes the <tt>ConcurrentHashMap</tt> instance from a
1468 * stream (i.e., deserializes it).
1469 * @param s the stream
1470 */
1471 @SuppressWarnings("unchecked")
1472 private void readObject(java.io.ObjectInputStream s)
1473 throws java.io.IOException, ClassNotFoundException {
1474 s.defaultReadObject();
1475
1476 // Re-initialize segments to be minimally sized, and let grow.
1477 int cap = MIN_SEGMENT_TABLE_CAPACITY;
1478 final Segment<K,V>[] segments = this.segments;
1479 for (int k = 0; k < segments.length; ++k) {
1480 Segment<K,V> seg = segments[k];
1481 if (seg != null) {
1482 seg.threshold = (int)(cap * seg.loadFactor);
1483 seg.table = (HashEntry<K,V>[]) new HashEntry<?,?>[cap];
1484 }
1485 }
1486
1487 // Read the keys and values, and put the mappings in the table
1488 for (;;) {
1489 K key = (K) s.readObject();
1490 V value = (V) s.readObject();
1491 if (key == null)
1492 break;
1493 put(key, value);
1494 }
1495 }
1496
1497 // Unsafe mechanics
1498 private static final sun.misc.Unsafe UNSAFE;
1499 private static final long SBASE;
1500 private static final int SSHIFT;
1501 private static final long TBASE;
1502 private static final int TSHIFT;
1503
1504 static {
1505 int ss, ts;
1506 try {
1507 UNSAFE = sun.misc.Unsafe.getUnsafe();
1508 Class<?> tc = HashEntry[].class;
1509 Class<?> sc = Segment[].class;
1510 TBASE = UNSAFE.arrayBaseOffset(tc);
1511 SBASE = UNSAFE.arrayBaseOffset(sc);
1512 ts = UNSAFE.arrayIndexScale(tc);
1513 ss = UNSAFE.arrayIndexScale(sc);
1514 } catch (Exception e) {
1515 throw new Error(e);
1516 }
1517 if ((ss & (ss-1)) != 0 || (ts & (ts-1)) != 0)
1518 throw new Error("data type scale not a power of two");
1519 SSHIFT = 31 - Integer.numberOfLeadingZeros(ss);
1520 TSHIFT = 31 - Integer.numberOfLeadingZeros(ts);
1521 }
1522
1523 }
|