0001: /*
0002: * Written by Doug Lea with assistance from members of JCP JSR-166
0003: * Expert Group and released to the public domain, as explained at
0004: * http://creativecommons.org/licenses/publicdomain
0005: */
0006:
0007: package java.util.concurrent;
0008:
0009: import java.util.concurrent.locks.*;
0010: import java.util.*;
0011: import java.io.Serializable;
0012: import java.io.IOException;
0013: import java.io.ObjectInputStream;
0014: import java.io.ObjectOutputStream;
0015:
0016: /**
0017: * A hash table supporting full concurrency of retrievals and
0018: * adjustable expected concurrency for updates. This class obeys the
0019: * same functional specification as {@link java.util.Hashtable}, and
0020: * includes versions of methods corresponding to each method of
0021: * <tt>Hashtable</tt>. However, even though all operations are
0022: * thread-safe, retrieval operations do <em>not</em> entail locking,
0023: * and there is <em>not</em> any support for locking the entire table
0024: * in a way that prevents all access. This class is fully
0025: * interoperable with <tt>Hashtable</tt> in programs that rely on its
0026: * thread safety but not on its synchronization details.
0027: *
0028: * <p> Retrieval operations (including <tt>get</tt>) generally do not
0029: * block, so may overlap with update operations (including
0030: * <tt>put</tt> and <tt>remove</tt>). Retrievals reflect the results
0031: * of the most recently <em>completed</em> update operations holding
0032: * upon their onset. For aggregate operations such as <tt>putAll</tt>
0033: * and <tt>clear</tt>, concurrent retrievals may reflect insertion or
0034: * removal of only some entries. Similarly, Iterators and
0035: * Enumerations return elements reflecting the state of the hash table
0036: * at some point at or since the creation of the iterator/enumeration.
0037: * They do <em>not</em> throw
0038: * {@link ConcurrentModificationException}. However, iterators are
0039: * designed to be used by only one thread at a time.
0040: *
0041: * <p> The allowed concurrency among update operations is guided by
0042: * the optional <tt>concurrencyLevel</tt> constructor argument
0043: * (default 16), which is used as a hint for internal sizing. The
0044: * table is internally partitioned to try to permit the indicated
0045: * number of concurrent updates without contention. Because placement
0046: * in hash tables is essentially random, the actual concurrency will
0047: * vary. Ideally, you should choose a value to accommodate as many
0048: * threads as will ever concurrently modify the table. Using a
0049: * significantly higher value than you need can waste space and time,
0050: * and a significantly lower value can lead to thread contention. But
0051: * overestimates and underestimates within an order of magnitude do
0052: * not usually have much noticeable impact. A value of one is
0053: * appropriate when it is known that only one thread will modify
0054: * and all others will only read.
0055: *
0056: * <p>This class implements all of the <em>optional</em> methods
0057: * of the {@link Map} and {@link Iterator} interfaces.
0058: *
0059: * <p> Like {@link java.util.Hashtable} but unlike {@link
0060: * java.util.HashMap}, this class does NOT allow <tt>null</tt> to be
0061: * used as a key or value.
0062: *
0063: * <p>This class is a member of the
0064: * <a href="{@docRoot}/../guide/collections/index.html">
0065: * Java Collections Framework</a>.
0066: *
0067: * @since 1.5
0068: * @author Doug Lea
0069: * @param <K> the type of keys maintained by this map
0070: * @param <V> the type of mapped values
0071: */
0072: public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
0073: implements ConcurrentMap<K, V>, Cloneable, Serializable {
0074: private static final long serialVersionUID = 7249069246763182397L;
0075:
0076: /*
0077: * The basic strategy is to subdivide the table among Segments,
0078: * each of which itself is a concurrently readable hash table.
0079: */
0080:
0081: /* ---------------- Constants -------------- */
0082:
0083: /**
0084: * The default initial number of table slots for this table.
0085: * Used when not otherwise specified in constructor.
0086: */
0087: static int DEFAULT_INITIAL_CAPACITY = 16;
0088:
0089: /**
0090: * The maximum capacity, used if a higher value is implicitly
0091: * specified by either of the constructors with arguments. MUST
0092: * be a power of two <= 1<<30 to ensure that entries are indexible
0093: * using ints.
0094: */
0095: static final int MAXIMUM_CAPACITY = 1 << 30;
0096:
0097: /**
0098: * The default load factor for this table. Used when not
0099: * otherwise specified in constructor.
0100: */
0101: static final float DEFAULT_LOAD_FACTOR = 0.75f;
0102:
0103: /**
0104: * The default number of concurrency control segments.
0105: **/
0106: static final int DEFAULT_SEGMENTS = 16;
0107:
0108: /**
0109: * The maximum number of segments to allow; used to bound
0110: * constructor arguments.
0111: */
0112: static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
0113:
0114: /* ---------------- Fields -------------- */
0115:
0116: /**
0117: * Mask value for indexing into segments. The upper bits of a
0118: * key's hash code are used to choose the segment.
0119: **/
0120: final int segmentMask;
0121:
0122: /**
0123: * Shift value for indexing within segments.
0124: **/
0125: final int segmentShift;
0126:
0127: /**
0128: * The segments, each of which is a specialized hash table
0129: */
0130: final Segment[] segments;
0131:
0132: transient Set<K> keySet;
0133: transient Set<Map.Entry<K, V>> entrySet;
0134: transient Collection<V> values;
0135:
0136: /* ---------------- Small Utilities -------------- */
0137:
0138: /**
0139: * Returns a hash code for non-null Object x.
0140: * Uses the same hash code spreader as most other java.util hash tables.
0141: * @param x the object serving as a key
0142: * @return the hash code
0143: */
0144: static int hash(Object x) {
0145: int h = x.hashCode();
0146: h += ~(h << 9);
0147: h ^= (h >>> 14);
0148: h += (h << 4);
0149: h ^= (h >>> 10);
0150: return h;
0151: }
0152:
0153: /**
0154: * Returns the segment that should be used for key with given hash
0155: * @param hash the hash code for the key
0156: * @return the segment
0157: */
0158: final Segment<K, V> segmentFor(int hash) {
0159: return (Segment<K, V>) segments[(hash >>> segmentShift)
0160: & segmentMask];
0161: }
0162:
0163: /* ---------------- Inner Classes -------------- */
0164:
0165: /**
0166: * Segments are specialized versions of hash tables. This
0167: * subclasses from ReentrantLock opportunistically, just to
0168: * simplify some locking and avoid separate construction.
0169: **/
0170: static final class Segment<K, V> extends ReentrantLock implements
0171: Serializable {
0172: /*
0173: * Segments maintain a table of entry lists that are ALWAYS
0174: * kept in a consistent state, so can be read without locking.
0175: * Next fields of nodes are immutable (final). All list
0176: * additions are performed at the front of each bin. This
0177: * makes it easy to check changes, and also fast to traverse.
0178: * When nodes would otherwise be changed, new nodes are
0179: * created to replace them. This works well for hash tables
0180: * since the bin lists tend to be short. (The average length
0181: * is less than two for the default load factor threshold.)
0182: *
0183: * Read operations can thus proceed without locking, but rely
0184: * on a memory barrier to ensure that completed write
0185: * operations performed by other threads are
0186: * noticed. Conveniently, the "count" field, tracking the
0187: * number of elements, can also serve as the volatile variable
0188: * providing proper read/write barriers. This is convenient
0189: * because this field needs to be read in many read operations
0190: * anyway.
0191: *
0192: * Implementors note. The basic rules for all this are:
0193: *
0194: * - All unsynchronized read operations must first read the
0195: * "count" field, and should not look at table entries if
0196: * it is 0.
0197: *
0198: * - All synchronized write operations should write to
0199: * the "count" field after updating. The operations must not
0200: * take any action that could even momentarily cause
0201: * a concurrent read operation to see inconsistent
0202: * data. This is made easier by the nature of the read
0203: * operations in Map. For example, no operation
0204: * can reveal that the table has grown but the threshold
0205: * has not yet been updated, so there are no atomicity
0206: * requirements for this with respect to reads.
0207: *
0208: * As a guide, all critical volatile reads and writes are marked
0209: * in code comments.
0210: */
0211:
0212: private static final long serialVersionUID = 2249069246763182397L;
0213:
0214: /**
0215: * The number of elements in this segment's region.
0216: **/
0217: transient volatile int count;
0218:
0219: /**
0220: * Number of updates; used for checking lack of modifications
0221: * in bulk-read methods.
0222: */
0223: transient int modCount;
0224:
0225: /**
0226: * The table is rehashed when its size exceeds this threshold.
0227: * (The value of this field is always (int)(capacity *
0228: * loadFactor).)
0229: */
0230: transient int threshold;
0231:
0232: /**
0233: * The per-segment table
0234: */
0235: transient HashEntry[] table;
0236:
0237: /**
0238: * The load factor for the hash table. Even though this value
0239: * is same for all segments, it is replicated to avoid needing
0240: * links to outer object.
0241: * @serial
0242: */
0243: final float loadFactor;
0244:
0245: Segment(int initialCapacity, float lf) {
0246: loadFactor = lf;
0247: setTable(new HashEntry[initialCapacity]);
0248: }
0249:
0250: /**
0251: * Set table to new HashEntry array.
0252: * Call only while holding lock or in constructor.
0253: **/
0254: void setTable(HashEntry[] newTable) {
0255: table = newTable;
0256: threshold = (int) (newTable.length * loadFactor);
0257: count = count; // write-volatile
0258: }
0259:
0260: /* Specialized implementations of map methods */
0261:
0262: V get(Object key, int hash) {
0263: if (count != 0) { // read-volatile
0264: HashEntry[] tab = table;
0265: int index = hash & (tab.length - 1);
0266: HashEntry<K, V> e = (HashEntry<K, V>) tab[index];
0267: while (e != null) {
0268: if (e.hash == hash && key.equals(e.key))
0269: return e.value;
0270: e = e.next;
0271: }
0272: }
0273: return null;
0274: }
0275:
0276: boolean containsKey(Object key, int hash) {
0277: if (count != 0) { // read-volatile
0278: HashEntry[] tab = table;
0279: int index = hash & (tab.length - 1);
0280: HashEntry<K, V> e = (HashEntry<K, V>) tab[index];
0281: while (e != null) {
0282: if (e.hash == hash && key.equals(e.key))
0283: return true;
0284: e = e.next;
0285: }
0286: }
0287: return false;
0288: }
0289:
0290: boolean containsValue(Object value) {
0291: if (count != 0) { // read-volatile
0292: HashEntry[] tab = table;
0293: int len = tab.length;
0294: for (int i = 0; i < len; i++)
0295: for (HashEntry<K, V> e = (HashEntry<K, V>) tab[i]; e != null; e = e.next)
0296: if (value.equals(e.value))
0297: return true;
0298: }
0299: return false;
0300: }
0301:
0302: boolean replace(K key, int hash, V oldValue, V newValue) {
0303: lock();
0304: try {
0305: int c = count;
0306: HashEntry[] tab = table;
0307: int index = hash & (tab.length - 1);
0308: HashEntry<K, V> first = (HashEntry<K, V>) tab[index];
0309: HashEntry<K, V> e = first;
0310: for (;;) {
0311: if (e == null)
0312: return false;
0313: if (e.hash == hash && key.equals(e.key))
0314: break;
0315: e = e.next;
0316: }
0317:
0318: V v = e.value;
0319: if (v == null || !oldValue.equals(v))
0320: return false;
0321:
0322: e.value = newValue;
0323: count = c; // write-volatile
0324: return true;
0325:
0326: } finally {
0327: unlock();
0328: }
0329: }
0330:
0331: V replace(K key, int hash, V newValue) {
0332: lock();
0333: try {
0334: int c = count;
0335: HashEntry[] tab = table;
0336: int index = hash & (tab.length - 1);
0337: HashEntry<K, V> first = (HashEntry<K, V>) tab[index];
0338: HashEntry<K, V> e = first;
0339: for (;;) {
0340: if (e == null)
0341: return null;
0342: if (e.hash == hash && key.equals(e.key))
0343: break;
0344: e = e.next;
0345: }
0346:
0347: V v = e.value;
0348: e.value = newValue;
0349: count = c; // write-volatile
0350: return v;
0351:
0352: } finally {
0353: unlock();
0354: }
0355: }
0356:
0357: V put(K key, int hash, V value, boolean onlyIfAbsent) {
0358: lock();
0359: try {
0360: int c = count;
0361: HashEntry[] tab = table;
0362: int index = hash & (tab.length - 1);
0363: HashEntry<K, V> first = (HashEntry<K, V>) tab[index];
0364:
0365: for (HashEntry<K, V> e = first; e != null; e = (HashEntry<K, V>) e.next) {
0366: if (e.hash == hash && key.equals(e.key)) {
0367: V oldValue = e.value;
0368: if (!onlyIfAbsent)
0369: e.value = value;
0370: ++modCount;
0371: count = c; // write-volatile
0372: return oldValue;
0373: }
0374: }
0375:
0376: tab[index] = new HashEntry<K, V>(hash, key, value,
0377: first);
0378: ++modCount;
0379: ++c;
0380: count = c; // write-volatile
0381: if (c > threshold)
0382: setTable(rehash(tab));
0383: return null;
0384: } finally {
0385: unlock();
0386: }
0387: }
0388:
0389: HashEntry[] rehash(HashEntry[] oldTable) {
0390: int oldCapacity = oldTable.length;
0391: if (oldCapacity >= MAXIMUM_CAPACITY)
0392: return oldTable;
0393:
0394: /*
0395: * Reclassify nodes in each list to new Map. Because we are
0396: * using power-of-two expansion, the elements from each bin
0397: * must either stay at same index, or move with a power of two
0398: * offset. We eliminate unnecessary node creation by catching
0399: * cases where old nodes can be reused because their next
0400: * fields won't change. Statistically, at the default
0401: * threshold, only about one-sixth of them need cloning when
0402: * a table doubles. The nodes they replace will be garbage
0403: * collectable as soon as they are no longer referenced by any
0404: * reader thread that may be in the midst of traversing table
0405: * right now.
0406: */
0407:
0408: HashEntry[] newTable = new HashEntry[oldCapacity << 1];
0409: int sizeMask = newTable.length - 1;
0410: for (int i = 0; i < oldCapacity; i++) {
0411: // We need to guarantee that any existing reads of old Map can
0412: // proceed. So we cannot yet null out each bin.
0413: HashEntry<K, V> e = (HashEntry<K, V>) oldTable[i];
0414:
0415: if (e != null) {
0416: HashEntry<K, V> next = e.next;
0417: int idx = e.hash & sizeMask;
0418:
0419: // Single node on list
0420: if (next == null)
0421: newTable[idx] = e;
0422:
0423: else {
0424: // Reuse trailing consecutive sequence at same slot
0425: HashEntry<K, V> lastRun = e;
0426: int lastIdx = idx;
0427: for (HashEntry<K, V> last = next; last != null; last = last.next) {
0428: int k = last.hash & sizeMask;
0429: if (k != lastIdx) {
0430: lastIdx = k;
0431: lastRun = last;
0432: }
0433: }
0434: newTable[lastIdx] = lastRun;
0435:
0436: // Clone all remaining nodes
0437: for (HashEntry<K, V> p = e; p != lastRun; p = p.next) {
0438: int k = p.hash & sizeMask;
0439: newTable[k] = new HashEntry<K, V>(p.hash,
0440: p.key, p.value,
0441: (HashEntry<K, V>) newTable[k]);
0442: }
0443: }
0444: }
0445: }
0446: return newTable;
0447: }
0448:
0449: /**
0450: * Remove; match on key only if value null, else match both.
0451: */
0452: V remove(Object key, int hash, Object value) {
0453: lock();
0454: try {
0455: int c = count;
0456: HashEntry[] tab = table;
0457: int index = hash & (tab.length - 1);
0458: HashEntry<K, V> first = (HashEntry<K, V>) tab[index];
0459:
0460: HashEntry<K, V> e = first;
0461: for (;;) {
0462: if (e == null)
0463: return null;
0464: if (e.hash == hash && key.equals(e.key))
0465: break;
0466: e = e.next;
0467: }
0468:
0469: V oldValue = e.value;
0470: if (value != null && !value.equals(oldValue))
0471: return null;
0472:
0473: // All entries following removed node can stay in list, but
0474: // all preceding ones need to be cloned.
0475: HashEntry<K, V> newFirst = e.next;
0476: for (HashEntry<K, V> p = first; p != e; p = p.next)
0477: newFirst = new HashEntry<K, V>(p.hash, p.key,
0478: p.value, newFirst);
0479: tab[index] = newFirst;
0480: ++modCount;
0481: count = c - 1; // write-volatile
0482: return oldValue;
0483: } finally {
0484: unlock();
0485: }
0486: }
0487:
0488: void clear() {
0489: lock();
0490: try {
0491: HashEntry[] tab = table;
0492: for (int i = 0; i < tab.length; i++)
0493: tab[i] = null;
0494: ++modCount;
0495: count = 0; // write-volatile
0496: } finally {
0497: unlock();
0498: }
0499: }
0500: }
0501:
0502: /**
0503: * ConcurrentHashMap list entry. Note that this is never exported
0504: * out as a user-visible Map.Entry
0505: */
0506: static final class HashEntry<K, V> {
0507: final K key;
0508: V value;
0509: final int hash;
0510: final HashEntry<K, V> next;
0511:
0512: HashEntry(int hash, K key, V value, HashEntry<K, V> next) {
0513: this .value = value;
0514: this .hash = hash;
0515: this .key = key;
0516: this .next = next;
0517: }
0518: }
0519:
0520: /* ---------------- Public operations -------------- */
0521:
0522: /**
0523: * Creates a new, empty map with the specified initial
0524: * capacity and the specified load factor.
0525: *
0526: * @param initialCapacity the initial capacity. The implementation
0527: * performs internal sizing to accommodate this many elements.
0528: * @param loadFactor the load factor threshold, used to control resizing.
0529: * @param concurrencyLevel the estimated number of concurrently
0530: * updating threads. The implementation performs internal sizing
0531: * to try to accommodate this many threads.
0532: * @throws IllegalArgumentException if the initial capacity is
0533: * negative or the load factor or concurrencyLevel are
0534: * nonpositive.
0535: */
0536: public ConcurrentHashMap(int initialCapacity, float loadFactor,
0537: int concurrencyLevel) {
0538: if (!(loadFactor > 0) || initialCapacity < 0
0539: || concurrencyLevel <= 0)
0540: throw new IllegalArgumentException();
0541:
0542: if (concurrencyLevel > MAX_SEGMENTS)
0543: concurrencyLevel = MAX_SEGMENTS;
0544:
0545: // Find power-of-two sizes best matching arguments
0546: int sshift = 0;
0547: int ssize = 1;
0548: while (ssize < concurrencyLevel) {
0549: ++sshift;
0550: ssize <<= 1;
0551: }
0552: segmentShift = 32 - sshift;
0553: segmentMask = ssize - 1;
0554: this .segments = new Segment[ssize];
0555:
0556: if (initialCapacity > MAXIMUM_CAPACITY)
0557: initialCapacity = MAXIMUM_CAPACITY;
0558: int c = initialCapacity / ssize;
0559: if (c * ssize < initialCapacity)
0560: ++c;
0561: int cap = 1;
0562: while (cap < c)
0563: cap <<= 1;
0564:
0565: for (int i = 0; i < this .segments.length; ++i)
0566: this .segments[i] = new Segment<K, V>(cap, loadFactor);
0567: }
0568:
0569: /**
0570: * Creates a new, empty map with the specified initial
0571: * capacity, and with default load factor and concurrencyLevel.
0572: *
0573: * @param initialCapacity The implementation performs internal
0574: * sizing to accommodate this many elements.
0575: * @throws IllegalArgumentException if the initial capacity of
0576: * elements is negative.
0577: */
0578: public ConcurrentHashMap(int initialCapacity) {
0579: this (initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
0580: }
0581:
0582: /**
0583: * Creates a new, empty map with a default initial capacity,
0584: * load factor, and concurrencyLevel.
0585: */
0586: public ConcurrentHashMap() {
0587: this (DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR,
0588: DEFAULT_SEGMENTS);
0589: }
0590:
0591: /**
0592: * Creates a new map with the same mappings as the given map. The
0593: * map is created with a capacity of twice the number of mappings in
0594: * the given map or 11 (whichever is greater), and a default load factor.
0595: * @param t the map
0596: */
0597: public ConcurrentHashMap(Map<? extends K, ? extends V> t) {
0598: this (Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1, 11),
0599: DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
0600: putAll(t);
0601: }
0602:
0603: // inherit Map javadoc
0604: public boolean isEmpty() {
0605: final Segment[] segments = this .segments;
0606: /*
0607: * We need to keep track of per-segment modCounts to avoid ABA
0608: * problems in which an element in one segment was added and
0609: * in another removed during traversal, in which case the
0610: * table was never actually empty at any point. Note the
0611: * similar use of modCounts in the size() and containsValue()
0612: * methods, which are the only other methods also susceptible
0613: * to ABA problems.
0614: */
0615: int[] mc = new int[segments.length];
0616: int mcsum = 0;
0617: for (int i = 0; i < segments.length; ++i) {
0618: if (segments[i].count != 0)
0619: return false;
0620: else
0621: mcsum += mc[i] = segments[i].modCount;
0622: }
0623: // If mcsum happens to be zero, then we know we got a snapshot
0624: // before any modifications at all were made. This is
0625: // probably common enough to bother tracking.
0626: if (mcsum != 0) {
0627: for (int i = 0; i < segments.length; ++i) {
0628: if (segments[i].count != 0
0629: || mc[i] != segments[i].modCount)
0630: return false;
0631: }
0632: }
0633: return true;
0634: }
0635:
0636: // inherit Map javadoc
0637: public int size() {
0638: final Segment[] segments = this .segments;
0639: int[] mc = new int[segments.length];
0640: for (;;) {
0641: long sum = 0;
0642: int mcsum = 0;
0643: for (int i = 0; i < segments.length; ++i) {
0644: sum += segments[i].count;
0645: mcsum += mc[i] = segments[i].modCount;
0646: }
0647: int check = 0;
0648: if (mcsum != 0) {
0649: for (int i = 0; i < segments.length; ++i) {
0650: check += segments[i].count;
0651: if (mc[i] != segments[i].modCount) {
0652: check = -1; // force retry
0653: break;
0654: }
0655: }
0656: }
0657: if (check == sum) {
0658: if (sum > Integer.MAX_VALUE)
0659: return Integer.MAX_VALUE;
0660: else
0661: return (int) sum;
0662: }
0663: }
0664: }
0665:
0666: /**
0667: * Returns the value to which the specified key is mapped in this table.
0668: *
0669: * @param key a key in the table.
0670: * @return the value to which the key is mapped in this table;
0671: * <tt>null</tt> if the key is not mapped to any value in
0672: * this table.
0673: * @throws NullPointerException if the key is
0674: * <tt>null</tt>.
0675: */
0676: public V get(Object key) {
0677: int hash = hash(key); // throws NullPointerException if key null
0678: return segmentFor(hash).get(key, hash);
0679: }
0680:
0681: /**
0682: * Tests if the specified object is a key in this table.
0683: *
0684: * @param key possible key.
0685: * @return <tt>true</tt> if and only if the specified object
0686: * is a key in this table, as determined by the
0687: * <tt>equals</tt> method; <tt>false</tt> otherwise.
0688: * @throws NullPointerException if the key is
0689: * <tt>null</tt>.
0690: */
0691: public boolean containsKey(Object key) {
0692: int hash = hash(key); // throws NullPointerException if key null
0693: return segmentFor(hash).containsKey(key, hash);
0694: }
0695:
0696: /**
0697: * Returns <tt>true</tt> if this map maps one or more keys to the
0698: * specified value. Note: This method requires a full internal
0699: * traversal of the hash table, and so is much slower than
0700: * method <tt>containsKey</tt>.
0701: *
0702: * @param value value whose presence in this map is to be tested.
0703: * @return <tt>true</tt> if this map maps one or more keys to the
0704: * specified value.
0705: * @throws NullPointerException if the value is <tt>null</tt>.
0706: */
0707: public boolean containsValue(Object value) {
0708: if (value == null)
0709: throw new NullPointerException();
0710:
0711: final Segment[] segments = this .segments;
0712: int[] mc = new int[segments.length];
0713: for (;;) {
0714: int sum = 0;
0715: int mcsum = 0;
0716: for (int i = 0; i < segments.length; ++i) {
0717: int c = segments[i].count;
0718: mcsum += mc[i] = segments[i].modCount;
0719: if (segments[i].containsValue(value))
0720: return true;
0721: }
0722: boolean cleanSweep = true;
0723: if (mcsum != 0) {
0724: for (int i = 0; i < segments.length; ++i) {
0725: int c = segments[i].count;
0726: if (mc[i] != segments[i].modCount) {
0727: cleanSweep = false;
0728: break;
0729: }
0730: }
0731: }
0732: if (cleanSweep)
0733: return false;
0734: }
0735: }
0736:
0737: /**
0738: * Legacy method testing if some key maps into the specified value
0739: * in this table. This method is identical in functionality to
0740: * {@link #containsValue}, and exists solely to ensure
0741: * full compatibility with class {@link java.util.Hashtable},
0742: * which supported this method prior to introduction of the
0743: * Java Collections framework.
0744:
0745: * @param value a value to search for.
0746: * @return <tt>true</tt> if and only if some key maps to the
0747: * <tt>value</tt> argument in this table as
0748: * determined by the <tt>equals</tt> method;
0749: * <tt>false</tt> otherwise.
0750: * @throws NullPointerException if the value is <tt>null</tt>.
0751: */
0752: public boolean contains(Object value) {
0753: return containsValue(value);
0754: }
0755:
0756: /**
0757: * Maps the specified <tt>key</tt> to the specified
0758: * <tt>value</tt> in this table. Neither the key nor the
0759: * value can be <tt>null</tt>.
0760: *
0761: * <p> The value can be retrieved by calling the <tt>get</tt> method
0762: * with a key that is equal to the original key.
0763: *
0764: * @param key the table key.
0765: * @param value the value.
0766: * @return the previous value of the specified key in this table,
0767: * or <tt>null</tt> if it did not have one.
0768: * @throws NullPointerException if the key or value is
0769: * <tt>null</tt>.
0770: */
0771: public V put(K key, V value) {
0772: if (value == null)
0773: throw new NullPointerException();
0774: int hash = hash(key);
0775: return segmentFor(hash).put(key, hash, value, false);
0776: }
0777:
0778: /**
0779: * If the specified key is not already associated
0780: * with a value, associate it with the given value.
0781: * This is equivalent to
0782: * <pre>
0783: * if (!map.containsKey(key))
0784: * return map.put(key, value);
0785: * else
0786: * return map.get(key);
0787: * </pre>
0788: * Except that the action is performed atomically.
0789: * @param key key with which the specified value is to be associated.
0790: * @param value value to be associated with the specified key.
0791: * @return previous value associated with specified key, or <tt>null</tt>
0792: * if there was no mapping for key. A <tt>null</tt> return can
0793: * also indicate that the map previously associated <tt>null</tt>
0794: * with the specified key, if the implementation supports
0795: * <tt>null</tt> values.
0796: *
0797: * @throws UnsupportedOperationException if the <tt>put</tt> operation is
0798: * not supported by this map.
0799: * @throws ClassCastException if the class of the specified key or value
0800: * prevents it from being stored in this map.
0801: * @throws NullPointerException if the specified key or value is
0802: * <tt>null</tt>.
0803: *
0804: **/
0805: public V putIfAbsent(K key, V value) {
0806: if (value == null)
0807: throw new NullPointerException();
0808: int hash = hash(key);
0809: return segmentFor(hash).put(key, hash, value, true);
0810: }
0811:
0812: /**
0813: * Copies all of the mappings from the specified map to this one.
0814: *
0815: * These mappings replace any mappings that this map had for any of the
0816: * keys currently in the specified Map.
0817: *
0818: * @param t Mappings to be stored in this map.
0819: */
0820: public void putAll(Map<? extends K, ? extends V> t) {
0821: for (Iterator<? extends Map.Entry<? extends K, ? extends V>> it = (Iterator<? extends Map.Entry<? extends K, ? extends V>>) t
0822: .entrySet().iterator(); it.hasNext();) {
0823: Entry<? extends K, ? extends V> e = it.next();
0824: put(e.getKey(), e.getValue());
0825: }
0826: }
0827:
0828: /**
0829: * Removes the key (and its corresponding value) from this
0830: * table. This method does nothing if the key is not in the table.
0831: *
0832: * @param key the key that needs to be removed.
0833: * @return the value to which the key had been mapped in this table,
0834: * or <tt>null</tt> if the key did not have a mapping.
0835: * @throws NullPointerException if the key is
0836: * <tt>null</tt>.
0837: */
0838: public V remove(Object key) {
0839: int hash = hash(key);
0840: return segmentFor(hash).remove(key, hash, null);
0841: }
0842:
0843: /**
0844: * Remove entry for key only if currently mapped to given value.
0845: * Acts as
0846: * <pre>
0847: * if (map.get(key).equals(value)) {
0848: * map.remove(key);
0849: * return true;
0850: * } else return false;
0851: * </pre>
0852: * except that the action is performed atomically.
0853: * @param key key with which the specified value is associated.
0854: * @param value value associated with the specified key.
0855: * @return true if the value was removed
0856: * @throws NullPointerException if the specified key is
0857: * <tt>null</tt>.
0858: */
0859: public boolean remove(Object key, Object value) {
0860: int hash = hash(key);
0861: return segmentFor(hash).remove(key, hash, value) != null;
0862: }
0863:
0864: /**
0865: * Replace entry for key only if currently mapped to given value.
0866: * Acts as
0867: * <pre>
0868: * if (map.get(key).equals(oldValue)) {
0869: * map.put(key, newValue);
0870: * return true;
0871: * } else return false;
0872: * </pre>
0873: * except that the action is performed atomically.
0874: * @param key key with which the specified value is associated.
0875: * @param oldValue value expected to be associated with the specified key.
0876: * @param newValue value to be associated with the specified key.
0877: * @return true if the value was replaced
0878: * @throws NullPointerException if the specified key or values are
0879: * <tt>null</tt>.
0880: */
0881: public boolean replace(K key, V oldValue, V newValue) {
0882: if (oldValue == null || newValue == null)
0883: throw new NullPointerException();
0884: int hash = hash(key);
0885: return segmentFor(hash).replace(key, hash, oldValue, newValue);
0886: }
0887:
0888: /**
0889: * Replace entry for key only if currently mapped to some value.
0890: * Acts as
0891: * <pre>
0892: * if ((map.containsKey(key)) {
0893: * return map.put(key, value);
0894: * } else return null;
0895: * </pre>
0896: * except that the action is performed atomically.
0897: * @param key key with which the specified value is associated.
0898: * @param value value to be associated with the specified key.
0899: * @return previous value associated with specified key, or <tt>null</tt>
0900: * if there was no mapping for key.
0901: * @throws NullPointerException if the specified key or value is
0902: * <tt>null</tt>.
0903: */
0904: public V replace(K key, V value) {
0905: if (value == null)
0906: throw new NullPointerException();
0907: int hash = hash(key);
0908: return segmentFor(hash).replace(key, hash, value);
0909: }
0910:
0911: /**
0912: * Removes all mappings from this map.
0913: */
0914: public void clear() {
0915: for (int i = 0; i < segments.length; ++i)
0916: segments[i].clear();
0917: }
0918:
0919: /**
0920: * Returns a shallow copy of this
0921: * <tt>ConcurrentHashMap</tt> instance: the keys and
0922: * values themselves are not cloned.
0923: *
0924: * @return a shallow copy of this map.
0925: */
0926: public Object clone() {
0927: // We cannot call super.clone, since it would share final
0928: // segments array, and there's no way to reassign finals.
0929:
0930: float lf = segments[0].loadFactor;
0931: int segs = segments.length;
0932: int cap = (int) (size() / lf);
0933: if (cap < segs)
0934: cap = segs;
0935: ConcurrentHashMap<K, V> t = new ConcurrentHashMap<K, V>(cap,
0936: lf, segs);
0937: t.putAll(this );
0938: return t;
0939: }
0940:
0941: /**
0942: * Returns a set view of the keys contained in this map. The set is
0943: * backed by the map, so changes to the map are reflected in the set, and
0944: * vice-versa. The set supports element removal, which removes the
0945: * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
0946: * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
0947: * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
0948: * <tt>addAll</tt> operations.
0949: * The returned <tt>iterator</tt> is a "weakly consistent" iterator that
0950: * will never throw {@link java.util.ConcurrentModificationException},
0951: * and guarantees to traverse elements as they existed upon
0952: * construction of the iterator, and may (but is not guaranteed to)
0953: * reflect any modifications subsequent to construction.
0954: *
0955: * @return a set view of the keys contained in this map.
0956: */
0957: public Set<K> keySet() {
0958: Set<K> ks = keySet;
0959: return (ks != null) ? ks : (keySet = new KeySet());
0960: }
0961:
0962: /**
0963: * Returns a collection view of the values contained in this map. The
0964: * collection is backed by the map, so changes to the map are reflected in
0965: * the collection, and vice-versa. The collection supports element
0966: * removal, which removes the corresponding mapping from this map, via the
0967: * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
0968: * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
0969: * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
0970: * The returned <tt>iterator</tt> is a "weakly consistent" iterator that
0971: * will never throw {@link java.util.ConcurrentModificationException},
0972: * and guarantees to traverse elements as they existed upon
0973: * construction of the iterator, and may (but is not guaranteed to)
0974: * reflect any modifications subsequent to construction.
0975: *
0976: * @return a collection view of the values contained in this map.
0977: */
0978: public Collection<V> values() {
0979: Collection<V> vs = values;
0980: return (vs != null) ? vs : (values = new Values());
0981: }
0982:
0983: /**
0984: * Returns a collection view of the mappings contained in this map. Each
0985: * element in the returned collection is a <tt>Map.Entry</tt>. The
0986: * collection is backed by the map, so changes to the map are reflected in
0987: * the collection, and vice-versa. The collection supports element
0988: * removal, which removes the corresponding mapping from the map, via the
0989: * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
0990: * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
0991: * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
0992: * The returned <tt>iterator</tt> is a "weakly consistent" iterator that
0993: * will never throw {@link java.util.ConcurrentModificationException},
0994: * and guarantees to traverse elements as they existed upon
0995: * construction of the iterator, and may (but is not guaranteed to)
0996: * reflect any modifications subsequent to construction.
0997: *
0998: * @return a collection view of the mappings contained in this map.
0999: */
1000: public Set<Map.Entry<K, V>> entrySet() {
1001: Set<Map.Entry<K, V>> es = entrySet;
1002: return (es != null) ? es
1003: : (entrySet = (Set<Map.Entry<K, V>>) (Set) new EntrySet());
1004: }
1005:
1006: /**
1007: * Returns an enumeration of the keys in this table.
1008: *
1009: * @return an enumeration of the keys in this table.
1010: * @see #keySet
1011: */
1012: public Enumeration<K> keys() {
1013: return new KeyIterator();
1014: }
1015:
1016: /**
1017: * Returns an enumeration of the values in this table.
1018: *
1019: * @return an enumeration of the values in this table.
1020: * @see #values
1021: */
1022: public Enumeration<V> elements() {
1023: return new ValueIterator();
1024: }
1025:
1026: /* ---------------- Iterator Support -------------- */
1027:
1028: abstract class HashIterator {
1029: int nextSegmentIndex;
1030: int nextTableIndex;
1031: HashEntry[] currentTable;
1032: HashEntry<K, V> nextEntry;
1033: HashEntry<K, V> lastReturned;
1034:
1035: HashIterator() {
1036: nextSegmentIndex = segments.length - 1;
1037: nextTableIndex = -1;
1038: advance();
1039: }
1040:
1041: public boolean hasMoreElements() {
1042: return hasNext();
1043: }
1044:
1045: final void advance() {
1046: if (nextEntry != null
1047: && (nextEntry = nextEntry.next) != null)
1048: return;
1049:
1050: while (nextTableIndex >= 0) {
1051: if ((nextEntry = (HashEntry<K, V>) currentTable[nextTableIndex--]) != null)
1052: return;
1053: }
1054:
1055: while (nextSegmentIndex >= 0) {
1056: Segment<K, V> seg = (Segment<K, V>) segments[nextSegmentIndex--];
1057: if (seg.count != 0) {
1058: currentTable = seg.table;
1059: for (int j = currentTable.length - 1; j >= 0; --j) {
1060: if ((nextEntry = (HashEntry<K, V>) currentTable[j]) != null) {
1061: nextTableIndex = j - 1;
1062: return;
1063: }
1064: }
1065: }
1066: }
1067: }
1068:
1069: public boolean hasNext() {
1070: return nextEntry != null;
1071: }
1072:
1073: HashEntry<K, V> nextEntry() {
1074: if (nextEntry == null)
1075: throw new NoSuchElementException();
1076: lastReturned = nextEntry;
1077: advance();
1078: return lastReturned;
1079: }
1080:
1081: public void remove() {
1082: if (lastReturned == null)
1083: throw new IllegalStateException();
1084: ConcurrentHashMap.this .remove(lastReturned.key);
1085: lastReturned = null;
1086: }
1087: }
1088:
1089: final class KeyIterator extends HashIterator implements
1090: Iterator<K>, Enumeration<K> {
1091: public K next() {
1092: return super .nextEntry().key;
1093: }
1094:
1095: public K nextElement() {
1096: return super .nextEntry().key;
1097: }
1098: }
1099:
1100: final class ValueIterator extends HashIterator implements
1101: Iterator<V>, Enumeration<V> {
1102: public V next() {
1103: return super .nextEntry().value;
1104: }
1105:
1106: public V nextElement() {
1107: return super .nextEntry().value;
1108: }
1109: }
1110:
1111: /**
1112: * Entry iterator. Exported Entry objects must write-through
1113: * changes in setValue, even if the nodes have been cloned. So we
1114: * cannot return internal HashEntry objects. Instead, the iterator
1115: * itself acts as a forwarding pseudo-entry.
1116: */
1117: final class EntryIterator extends HashIterator implements
1118: Map.Entry<K, V>, Iterator<Entry<K, V>> {
1119: public Map.Entry<K, V> next() {
1120: nextEntry();
1121: return this ;
1122: }
1123:
1124: public K getKey() {
1125: if (lastReturned == null)
1126: throw new IllegalStateException("Entry was removed");
1127: return lastReturned.key;
1128: }
1129:
1130: public V getValue() {
1131: if (lastReturned == null)
1132: throw new IllegalStateException("Entry was removed");
1133: return ConcurrentHashMap.this .get(lastReturned.key);
1134: }
1135:
1136: public V setValue(V value) {
1137: if (lastReturned == null)
1138: throw new IllegalStateException("Entry was removed");
1139: return ConcurrentHashMap.this .put(lastReturned.key, value);
1140: }
1141:
1142: public boolean equals(Object o) {
1143: // If not acting as entry, just use default.
1144: if (lastReturned == null)
1145: return super .equals(o);
1146: if (!(o instanceof Map.Entry))
1147: return false;
1148: Map.Entry e = (Map.Entry) o;
1149: return eq(getKey(), e.getKey())
1150: && eq(getValue(), e.getValue());
1151: }
1152:
1153: public int hashCode() {
1154: // If not acting as entry, just use default.
1155: if (lastReturned == null)
1156: return super .hashCode();
1157:
1158: Object k = getKey();
1159: Object v = getValue();
1160: return ((k == null) ? 0 : k.hashCode())
1161: ^ ((v == null) ? 0 : v.hashCode());
1162: }
1163:
1164: public String toString() {
1165: // If not acting as entry, just use default.
1166: if (lastReturned == null)
1167: return super .toString();
1168: else
1169: return getKey() + "=" + getValue();
1170: }
1171:
1172: boolean eq(Object o1, Object o2) {
1173: return (o1 == null ? o2 == null : o1.equals(o2));
1174: }
1175:
1176: }
1177:
1178: final class KeySet extends AbstractSet<K> {
1179: public Iterator<K> iterator() {
1180: return new KeyIterator();
1181: }
1182:
1183: public int size() {
1184: return ConcurrentHashMap.this .size();
1185: }
1186:
1187: public boolean contains(Object o) {
1188: return ConcurrentHashMap.this .containsKey(o);
1189: }
1190:
1191: public boolean remove(Object o) {
1192: return ConcurrentHashMap.this .remove(o) != null;
1193: }
1194:
1195: public void clear() {
1196: ConcurrentHashMap.this .clear();
1197: }
1198: }
1199:
1200: final class Values extends AbstractCollection<V> {
1201: public Iterator<V> iterator() {
1202: return new ValueIterator();
1203: }
1204:
1205: public int size() {
1206: return ConcurrentHashMap.this .size();
1207: }
1208:
1209: public boolean contains(Object o) {
1210: return ConcurrentHashMap.this .containsValue(o);
1211: }
1212:
1213: public void clear() {
1214: ConcurrentHashMap.this .clear();
1215: }
1216: }
1217:
1218: final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
1219: public Iterator<Map.Entry<K, V>> iterator() {
1220: return new EntryIterator();
1221: }
1222:
1223: public boolean contains(Object o) {
1224: if (!(o instanceof Map.Entry))
1225: return false;
1226: Map.Entry<K, V> e = (Map.Entry<K, V>) o;
1227: V v = ConcurrentHashMap.this .get(e.getKey());
1228: return v != null && v.equals(e.getValue());
1229: }
1230:
1231: public boolean remove(Object o) {
1232: if (!(o instanceof Map.Entry))
1233: return false;
1234: Map.Entry<K, V> e = (Map.Entry<K, V>) o;
1235: return ConcurrentHashMap.this .remove(e.getKey(), e
1236: .getValue());
1237: }
1238:
1239: public int size() {
1240: return ConcurrentHashMap.this .size();
1241: }
1242:
1243: public void clear() {
1244: ConcurrentHashMap.this .clear();
1245: }
1246:
1247: public Object[] toArray() {
1248: // Since we don't ordinarily have distinct Entry objects, we
1249: // must pack elements using exportable SimpleEntry
1250: Collection<Map.Entry<K, V>> c = new ArrayList<Map.Entry<K, V>>(
1251: size());
1252: for (Iterator<Map.Entry<K, V>> i = iterator(); i.hasNext();)
1253: c.add(new SimpleEntry<K, V>(i.next()));
1254: return c.toArray();
1255: }
1256:
1257: public <T> T[] toArray(T[] a) {
1258: Collection<Map.Entry<K, V>> c = new ArrayList<Map.Entry<K, V>>(
1259: size());
1260: for (Iterator<Map.Entry<K, V>> i = iterator(); i.hasNext();)
1261: c.add(new SimpleEntry<K, V>(i.next()));
1262: return c.toArray(a);
1263: }
1264:
1265: }
1266:
1267: /**
1268: * This duplicates java.util.AbstractMap.SimpleEntry until this class
1269: * is made accessible.
1270: */
1271: static final class SimpleEntry<K, V> implements Entry<K, V> {
1272: K key;
1273: V value;
1274:
1275: public SimpleEntry(K key, V value) {
1276: this .key = key;
1277: this .value = value;
1278: }
1279:
1280: public SimpleEntry(Entry<K, V> e) {
1281: this .key = e.getKey();
1282: this .value = e.getValue();
1283: }
1284:
1285: public K getKey() {
1286: return key;
1287: }
1288:
1289: public V getValue() {
1290: return value;
1291: }
1292:
1293: public V setValue(V value) {
1294: V oldValue = this .value;
1295: this .value = value;
1296: return oldValue;
1297: }
1298:
1299: public boolean equals(Object o) {
1300: if (!(o instanceof Map.Entry))
1301: return false;
1302: Map.Entry e = (Map.Entry) o;
1303: return eq(key, e.getKey()) && eq(value, e.getValue());
1304: }
1305:
1306: public int hashCode() {
1307: return ((key == null) ? 0 : key.hashCode())
1308: ^ ((value == null) ? 0 : value.hashCode());
1309: }
1310:
1311: public String toString() {
1312: return key + "=" + value;
1313: }
1314:
1315: static boolean eq(Object o1, Object o2) {
1316: return (o1 == null ? o2 == null : o1.equals(o2));
1317: }
1318: }
1319:
1320: /* ---------------- Serialization Support -------------- */
1321:
1322: /**
1323: * Save the state of the <tt>ConcurrentHashMap</tt>
1324: * instance to a stream (i.e.,
1325: * serialize it).
1326: * @param s the stream
1327: * @serialData
1328: * the key (Object) and value (Object)
1329: * for each key-value mapping, followed by a null pair.
1330: * The key-value mappings are emitted in no particular order.
1331: */
1332: private void writeObject(java.io.ObjectOutputStream s)
1333: throws IOException {
1334: s.defaultWriteObject();
1335:
1336: for (int k = 0; k < segments.length; ++k) {
1337: Segment<K, V> seg = (Segment<K, V>) segments[k];
1338: seg.lock();
1339: try {
1340: HashEntry[] tab = seg.table;
1341: for (int i = 0; i < tab.length; ++i) {
1342: for (HashEntry<K, V> e = (HashEntry<K, V>) tab[i]; e != null; e = e.next) {
1343: s.writeObject(e.key);
1344: s.writeObject(e.value);
1345: }
1346: }
1347: } finally {
1348: seg.unlock();
1349: }
1350: }
1351: s.writeObject(null);
1352: s.writeObject(null);
1353: }
1354:
1355: /**
1356: * Reconstitute the <tt>ConcurrentHashMap</tt>
1357: * instance from a stream (i.e.,
1358: * deserialize it).
1359: * @param s the stream
1360: */
1361: private void readObject(java.io.ObjectInputStream s)
1362: throws IOException, ClassNotFoundException {
1363: s.defaultReadObject();
1364:
1365: // Initialize each segment to be minimally sized, and let grow.
1366: for (int i = 0; i < segments.length; ++i) {
1367: segments[i].setTable(new HashEntry[1]);
1368: }
1369:
1370: // Read the keys and values, and put the mappings in the table
1371: for (;;) {
1372: K key = (K) s.readObject();
1373: V value = (V) s.readObject();
1374: if (key == null)
1375: break;
1376: put(key, value);
1377: }
1378: }
1379: }
|