0001: /*
0002: File: ConcurrentHashMap
0003:
0004: Written by Doug Lea. Adapted and released, under explicit
0005: permission, from JDK1.2 HashMap.java and Hashtable.java which
0006: carries the following copyright:
0007:
0008: * Copyright 1997 by Sun Microsystems, Inc.,
0009: * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
0010: * All rights reserved.
0011: *
0012: * This software is the confidential and proprietary information
0013: * of Sun Microsystems, Inc. ("Confidential Information"). You
0014: * shall not disclose such Confidential Information and shall use
0015: * it only in accordance with the terms of the license agreement
0016: * you entered into with Sun.
0017:
0018: History:
0019: Date Who What
0020: 26nov2000 dl Created, based on ConcurrentReaderHashMap
0021: 12jan2001 dl public release
0022: 17nov2001 dl Minor tunings
0023: 24oct2003 dl Segment implements Serializable
0024: */
0025:
0026: package wicket.util.concurrent;
0027:
0028: import java.io.IOException;
0029: import java.io.Serializable;
0030: import java.util.AbstractCollection;
0031: import java.util.AbstractMap;
0032: import java.util.AbstractSet;
0033: import java.util.Collection;
0034: import java.util.Enumeration;
0035: import java.util.Iterator;
0036: import java.util.Map;
0037: import java.util.NoSuchElementException;
0038: import java.util.Set;
0039:
0040: /**
0041: * A version of Hashtable supporting concurrency for both retrievals and
0042: * updates:
0043: *
0044: * <dl>
0045: * <dt> Retrievals
0046: *
0047: * <dd> Retrievals may overlap updates. (This is the same policy as
0048: * ConcurrentReaderHashMap.) Successful retrievals using get(key) and
0049: * containsKey(key) usually run without locking. Unsuccessful retrievals (i.e.,
0050: * when the key is not present) do involve brief synchronization (locking).
0051: * Because retrieval operations can ordinarily overlap with update operations
0052: * (i.e., put, remove, and their derivatives), retrievals can only be guaranteed
0053: * to return the results of the most recently <em>completed</em> operations
0054: * holding upon their onset. Retrieval operations may or may not return results
0055: * reflecting in-progress writing operations. However, the retrieval operations
0056: * do always return consistent results -- either those holding before any single
0057: * modification or after it, but never a nonsense result. For aggregate
0058: * operations such as putAll and clear, concurrent reads may reflect insertion
0059: * or removal of only some entries.
0060: * <p>
0061: *
0062: * Iterators and Enumerations (i.e., those returned by keySet().iterator(),
0063: * entrySet().iterator(), values().iterator(), keys(), and elements()) return
0064: * elements reflecting the state of the hash table at some point at or since the
0065: * creation of the iterator/enumeration. They will return at most one instance
0066: * of each element (via next()/nextElement()), but might or might not reflect
0067: * puts and removes that have been processed since they were created. They do
0068: * <em>not</em> throw ConcurrentModificationException. However, these
0069: * iterators are designed to be used by only one thread at a time. Passing an
0070: * iterator across multiple threads may lead to unpredictable results if the
0071: * table is being concurrently modified.
0072: * <p>
0073: *
0074: *
0075: * <dt> Updates
0076: *
0077: * <dd> This class supports a hard-wired preset <em>concurrency
0078: * level</em> of
0079: * 32. This allows a maximum of 32 put and/or remove operations to proceed
0080: * concurrently. This level is an upper bound on concurrency, not a guarantee,
0081: * since it interacts with how well-strewn elements are across bins of the
0082: * table. (The preset value in part reflects the fact that even on large
0083: * multiprocessors, factors other than synchronization tend to be bottlenecks
0084: * when more than 32 threads concurrently attempt updates.) Additionally,
0085: * operations triggering internal resizing and clearing do not execute
0086: * concurrently with any operation.
0087: * <p>
0088: *
0089: * There is <em>NOT</em> any support for locking the entire table to prevent
0090: * updates. This makes it imposssible, for example, to add an element only if it
0091: * is not already present, since another thread may be in the process of doing
0092: * the same thing. If you need such capabilities, consider instead using the
0093: * ConcurrentReaderHashMap class.
0094: *
0095: * </dl>
0096: *
0097: * Because of how concurrency control is split up, the size() and isEmpty()
0098: * methods require accumulations across 32 control segments, and so might be
0099: * slightly slower than you expect.
0100: * <p>
0101: *
0102: * This class may be used as a direct replacement for java.util.Hashtable in any
0103: * application that does not rely on the ability to lock the entire table to
0104: * prevent updates. As of this writing, it performs much faster than Hashtable
0105: * in typical multi-threaded applications with multiple readers and writers.
0106: * Like Hashtable but unlike java.util.HashMap, this class does NOT allow
0107: * <tt>null</tt> to be used as a key or value.
0108: * <p>
0109: *
0110: * Implementation note: A slightly faster implementation of this class will be
0111: * possible once planned Java Memory Model revisions are in place.
0112: *
0113: * <p>[<a
0114: * href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html">
0115: * Introduction to this package. </a>]
0116: *
0117: */
0118:
0119: public class ConcurrentHashMap extends AbstractMap implements Map,
0120: Cloneable, Serializable {
0121: private static final long serialVersionUID = 1L;
0122:
0123: /*
0124: * The basic strategy is an optimistic-style scheme based on the guarantee
0125: * that the hash table and its lists are always kept in a consistent enough
0126: * state to be read without locking:
0127: *
0128: * Read operations first proceed without locking, by traversing the
0129: * apparently correct list of the apparently correct bin. If an entry is
0130: * found, but not invalidated (value field null), it is returned. If not
0131: * found, operations must recheck (after a memory barrier) to make sure they
0132: * are using both the right list and the right table (which can change under
0133: * resizes). If invalidated, reads must acquire main update lock to wait out
0134: * the update, and then re-traverse.
0135: *
0136: * All list additions are at the front of each bin, making it easy to check
0137: * changes, and also fast to traverse. Entry next pointers are never
0138: * assigned. Remove() builds new nodes when necessary to preserve this.
0139: *
0140: * Remove() (also clear()) invalidates removed nodes to alert read
0141: * operations that they must wait out the full modifications.
0142: *
0143: * Locking for puts, removes (and, when necessary gets, etc) is controlled
0144: * by Segments, each covering a portion of the table. During operations
0145: * requiring global exclusivity (mainly resize and clear), ALL of these
0146: * locks are acquired at once. Note that these segments are NOT contiguous --
0147: * they are based on the least 5 bits of hashcodes. This ensures that the
0148: * same segment controls the same slots before and after resizing, which is
0149: * necessary for supporting concurrent retrievals. This comes at the price
0150: * of a mismatch of logical vs physical locality, but this seems not to be a
0151: * performance problem in practice.
0152: *
0153: */
0154:
0155: /**
0156: * The hash table data.
0157: */
0158: protected transient Entry[] table;
0159:
0160: /**
0161: * The number of concurrency control segments. The value can be at most 32
0162: * since ints are used as bitsets over segments. Emprically, it doesn't seem
0163: * to pay to decrease it either, so the value should be at least 32. In
0164: * other words, do not redefine this :-)
0165: */
0166: protected static final int CONCURRENCY_LEVEL = 32;
0167:
0168: /**
0169: * Mask value for indexing into segments
0170: */
0171: protected static final int SEGMENT_MASK = CONCURRENCY_LEVEL - 1;
0172:
0173: /**
0174: * Bookkeeping for each concurrency control segment. Each segment contains a
0175: * local count of the number of elements in its region. However, the main
0176: * use of a Segment is for its lock.
0177: */
0178: protected final static class Segment implements Serializable {
0179: private static final long serialVersionUID = 1L;
0180:
0181: /**
0182: * The number of elements in this segment's region. It is always updated
0183: * within synchronized blocks.
0184: */
0185: protected int count;
0186:
0187: /**
0188: * Get the count under synch.
0189: * @return count under sync
0190: */
0191: protected synchronized int getCount() {
0192: return count;
0193: }
0194:
0195: /**
0196: * Force a synchronization
0197: */
0198: protected synchronized void synch() {
0199: }
0200: }
0201:
0202: /**
0203: * The array of concurrency control segments.
0204: */
0205:
0206: protected final Segment[] segments = new Segment[CONCURRENCY_LEVEL];
0207:
0208: /**
0209: * The default initial number of table slots for this table (32). Used when
0210: * not otherwise specified in constructor.
0211: */
0212: public static final int DEFAULT_INITIAL_CAPACITY = 32;
0213:
0214: /**
0215: * The minimum capacity, used if a lower value is implicitly specified by
0216: * either of the constructors with arguments. MUST be a power of two.
0217: */
0218: private static final int MINIMUM_CAPACITY = 32;
0219:
0220: /**
0221: * The maximum capacity, used if a higher value is implicitly specified by
0222: * either of the constructors with arguments. MUST be a power of two <= 1<<30.
0223: */
0224: private static final int MAXIMUM_CAPACITY = 1 << 30;
0225:
0226: /**
0227: * The default load factor for this table (0.75) Used when not otherwise
0228: * specified in constructor.
0229: */
0230: public static final float DEFAULT_LOAD_FACTOR = 0.75f;
0231:
0232: /**
0233: * The load factor for the hash table.
0234: *
0235: * @serial
0236: */
0237: protected final float loadFactor;
0238:
0239: /**
0240: * Per-segment resize threshold.
0241: *
0242: * @serial
0243: */
0244: protected int threshold;
0245:
0246: /**
0247: * Number of segments voting for resize. The table is doubled when 1/4 of
0248: * the segments reach threshold. Volatile but updated without synch since
0249: * this is just a heuristic.
0250: */
0251: protected transient volatile int votesForResize;
0252:
0253: /**
0254: * Return the number of set bits in w. For a derivation of this algorithm,
0255: * see "Algorithms and data structures with applications to graphics and
0256: * geometry", by Jurg Nievergelt and Klaus Hinrichs, Prentice Hall, 1993.
0257: * See also notes by Torsten Sillke at
0258: * http://www.mathematik.uni-bielefeld.de/~sillke/PROBLEMS/bitcount
0259: * @param w arg
0260: * @return number of set bits
0261: */
0262: protected static int bitcount(int w) {
0263: w -= (0xaaaaaaaa & w) >>> 1;
0264: w = (w & 0x33333333) + ((w >>> 2) & 0x33333333);
0265: w = (w + (w >>> 4)) & 0x0f0f0f0f;
0266: w += w >>> 8;
0267: w += w >>> 16;
0268: return w & 0xff;
0269: }
0270:
0271: /**
0272: * Returns the appropriate capacity (power of two) for the specified initial
0273: * capacity argument.
0274: * @param initialCapacity the initial capacity
0275: * @return appropriate capacity
0276: */
0277: private int p2capacity(int initialCapacity) {
0278: int cap = initialCapacity;
0279:
0280: // Compute the appropriate capacity
0281: int result;
0282: if (cap > MAXIMUM_CAPACITY || cap < 0) {
0283: result = MAXIMUM_CAPACITY;
0284: } else {
0285: result = MINIMUM_CAPACITY;
0286: while (result < cap) {
0287: result <<= 1;
0288: }
0289: }
0290: return result;
0291: }
0292:
0293: /**
0294: * Return hash code for Object x. Since we are using power-of-two tables, it
0295: * is worth the effort to improve hashcode via the same multiplicative
0296: * scheme as used in IdentityHashMap.
0297: * @param x
0298: * @return hash code
0299: */
0300: protected static int hash(Object x) {
0301: int h = x.hashCode();
0302: // Multiply by 127 (quickly, via shifts), and mix in some high
0303: // bits to help guard against bunching of codes that are
0304: // consecutive or equally spaced.
0305: return ((h << 7) - h + (h >>> 9) + (h >>> 17));
0306: }
0307:
0308: /**
0309: * Check for equality of non-null references x and y.
0310: * @param x ref
0311: * @param y ref
0312: * @return is equal
0313: */
0314: protected boolean eq(Object x, Object y) {
0315: return x == y || x.equals(y);
0316: }
0317:
0318: /**
0319: * Create table array and set the per-segment threshold *
0320: * @param capacity
0321: * @return table array
0322: */
0323: protected Entry[] newTable(int capacity) {
0324: threshold = (int) (capacity * loadFactor / CONCURRENCY_LEVEL) + 1;
0325: return new Entry[capacity];
0326: }
0327:
0328: /**
0329: * Constructs a new, empty map with the specified initial capacity and the
0330: * specified load factor.
0331: *
0332: * @param initialCapacity
0333: * the initial capacity. The actual initial capacity is rounded
0334: * to the nearest power of two.
0335: * @param loadFactor
0336: * the load factor threshold, used to control resizing. This
0337: * value is used in an approximate way: When at least a quarter
0338: * of the segments of the table reach per-segment threshold, or
0339: * one of the segments itself exceeds overall threshold, the
0340: * table is doubled. This will on average cause resizing when the
0341: * table-wide load factor is slightly less than the threshold. If
0342: * you'd like to avoid resizing, you can set this to a
0343: * ridiculously large value.
0344: * @throws IllegalArgumentException
0345: * if the load factor is nonpositive.
0346: */
0347: public ConcurrentHashMap(int initialCapacity, float loadFactor) {
0348: if (!(loadFactor > 0)) {
0349: throw new IllegalArgumentException("Illegal Load factor: "
0350: + loadFactor);
0351: }
0352: this .loadFactor = loadFactor;
0353: for (int i = 0; i < segments.length; ++i) {
0354: segments[i] = new Segment();
0355: }
0356: int cap = p2capacity(initialCapacity);
0357: table = newTable(cap);
0358: }
0359:
0360: /**
0361: * Constructs a new, empty map with the specified initial capacity and
0362: * default load factor.
0363: *
0364: * @param initialCapacity
0365: * the initial capacity of the ConcurrentHashMap.
0366: * @throws IllegalArgumentException
0367: * if the initial maximum number of elements is less than zero.
0368: */
0369: public ConcurrentHashMap(int initialCapacity) {
0370: this (initialCapacity, DEFAULT_LOAD_FACTOR);
0371: }
0372:
0373: /**
0374: * Constructs a new, empty map with a default initial capacity and default
0375: * load factor.
0376: */
0377: public ConcurrentHashMap() {
0378: this (DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
0379: }
0380:
0381: /**
0382: * Constructs a new map with the same mappings as the given map. The map is
0383: * created with a capacity of twice the number of mappings in the given map
0384: * or 32 (whichever is greater), and a default load factor.
0385: * @param t map to copy
0386: */
0387: public ConcurrentHashMap(Map t) {
0388: this (Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1,
0389: MINIMUM_CAPACITY), DEFAULT_LOAD_FACTOR);
0390: putAll(t);
0391: }
0392:
0393: /**
0394: * Returns the number of key-value mappings in this map.
0395: *
0396: * @return the number of key-value mappings in this map.
0397: */
0398: public int size() {
0399: int c = 0;
0400: for (int i = 0; i < segments.length; ++i) {
0401: c += segments[i].getCount();
0402: }
0403: return c;
0404: }
0405:
0406: /**
0407: * Returns <tt>true</tt> if this map contains no key-value mappings.
0408: *
0409: * @return <tt>true</tt> if this map contains no key-value mappings.
0410: */
0411: public boolean isEmpty() {
0412: for (int i = 0; i < segments.length; ++i) {
0413: if (segments[i].getCount() != 0) {
0414: return false;
0415: }
0416: }
0417: return true;
0418: }
0419:
0420: /**
0421: * Returns the value to which the specified key is mapped in this table.
0422: *
0423: * @param key
0424: * a key in the table.
0425: * @return the value to which the key is mapped in this table;
0426: * <code>null</code> if the key is not mapped to any value in this
0427: * table.
0428: * @exception NullPointerException
0429: * if the key is <code>null</code>.
0430: * @see #put(Object, Object)
0431: */
0432: public Object get(Object key) {
0433: int hash = hash(key); // throws null pointer exception if key null
0434:
0435: // Try first without locking...
0436: Entry[] tab = table;
0437: int index = hash & (tab.length - 1);
0438: Entry first = tab[index];
0439: Entry e;
0440:
0441: for (e = first; e != null; e = e.next) {
0442: if (e.hash == hash && eq(key, e.key)) {
0443: Object value = e.value;
0444: if (value != null) {
0445: return value;
0446: } else {
0447: break;
0448: }
0449: }
0450: }
0451:
0452: // Recheck under synch if key apparently not there or interference
0453: Segment seg = segments[hash & SEGMENT_MASK];
0454: synchronized (seg) {
0455: tab = table;
0456: index = hash & (tab.length - 1);
0457: Entry newFirst = tab[index];
0458: if (e != null || first != newFirst) {
0459: for (e = newFirst; e != null; e = e.next) {
0460: if (e.hash == hash && eq(key, e.key)) {
0461: return e.value;
0462: }
0463: }
0464: }
0465: return null;
0466: }
0467: }
0468:
0469: /**
0470: * Tests if the specified object is a key in this table.
0471: *
0472: * @param key
0473: * possible key.
0474: * @return <code>true</code> if and only if the specified object is a key
0475: * in this table, as determined by the <tt>equals</tt> method;
0476: * <code>false</code> otherwise.
0477: * @exception NullPointerException
0478: * if the key is <code>null</code>.
0479: * @see #contains(Object)
0480: */
0481: public boolean containsKey(Object key) {
0482: return get(key) != null;
0483: }
0484:
0485: /**
0486: * Maps the specified <code>key</code> to the specified <code>value</code>
0487: * in this table. Neither the key nor the value can be <code>null</code>.
0488: * (Note that this policy is the same as for java.util.Hashtable, but unlike
0489: * java.util.HashMap, which does accept nulls as valid keys and values.)
0490: * <p>
0491: *
0492: * The value can be retrieved by calling the <code>get</code> method with
0493: * a key that is equal to the original key.
0494: *
0495: * @param key
0496: * the table key.
0497: * @param value
0498: * the value.
0499: * @return the previous value of the specified key in this table, or
0500: * <code>null</code> if it did not have one.
0501: * @exception NullPointerException
0502: * if the key or value is <code>null</code>.
0503: * @see Object#equals(Object)
0504: * @see #get(Object)
0505: */
0506: public Object put(Object key, Object value) {
0507: if (value == null) {
0508: throw new IllegalArgumentException("Value must not be null");
0509: }
0510: int hash = hash(key);
0511: Segment seg = segments[hash & SEGMENT_MASK];
0512: int segcount;
0513: Entry[] tab;
0514: int votes;
0515:
0516: synchronized (seg) {
0517: tab = table;
0518: int index = hash & (tab.length - 1);
0519: Entry first = tab[index];
0520:
0521: for (Entry e = first; e != null; e = e.next) {
0522: if (e.hash == hash && eq(key, e.key)) {
0523: Object oldValue = e.value;
0524: e.value = value;
0525: return oldValue;
0526: }
0527: }
0528:
0529: // Add to front of list
0530: Entry newEntry = new Entry(hash, key, value, first);
0531: tab[index] = newEntry;
0532:
0533: if ((segcount = ++seg.count) < threshold) {
0534: return null;
0535: }
0536:
0537: int bit = (1 << (hash & SEGMENT_MASK));
0538: votes = votesForResize;
0539: if ((votes & bit) == 0) {
0540: votes = votesForResize |= bit;
0541: }
0542: }
0543:
0544: // Attempt resize if 1/4 segs vote,
0545: // or if this seg itself reaches the overall threshold.
0546: // (The latter check is just a safeguard to avoid pathological cases.)
0547: if (bitcount(votes) >= CONCURRENCY_LEVEL / 4
0548: || segcount > (threshold * CONCURRENCY_LEVEL)) {
0549: resize(0, tab);
0550: }
0551:
0552: return null;
0553: }
0554:
0555: /**
0556: * Gather all locks in order to call rehash, by recursing within synch
0557: * blocks for each segment index.
0558: *
0559: * @param index
0560: * the current segment. initially call value must be 0
0561: * @param assumedTab
0562: * the state of table on first call to resize. If this changes on
0563: * any call, the attempt is aborted because the table has already
0564: * been resized by another thread.
0565: */
0566: protected void resize(int index, Entry[] assumedTab) {
0567: Segment seg = segments[index];
0568: synchronized (seg) {
0569: if (assumedTab == table) {
0570: int next = index + 1;
0571: if (next < segments.length) {
0572: resize(next, assumedTab);
0573: } else {
0574: rehash();
0575: }
0576: }
0577: }
0578: }
0579:
0580: /**
0581: * Rehashes the contents of this map into a new table with a larger
0582: * capacity.
0583: */
0584: protected void rehash() {
0585: votesForResize = 0; // reset
0586:
0587: Entry[] oldTable = table;
0588: int oldCapacity = oldTable.length;
0589:
0590: if (oldCapacity >= MAXIMUM_CAPACITY) {
0591: threshold = Integer.MAX_VALUE; // avoid retriggering
0592: return;
0593: }
0594:
0595: int newCapacity = oldCapacity << 1;
0596: Entry[] newTable = newTable(newCapacity);
0597: int mask = newCapacity - 1;
0598:
0599: /*
0600: * Reclassify nodes in each list to new Map. Because we are using
0601: * power-of-two expansion, the elements from each bin must either stay
0602: * at same index, or move to oldCapacity+index. We also eliminate
0603: * unnecessary node creation by catching cases where old nodes can be
0604: * reused because their next fields won't change. Statistically, at the
0605: * default threshhold, only about one-sixth of them need cloning. (The
0606: * nodes they replace will be garbage collectable as soon as they are no
0607: * longer referenced by any reader thread that may be in the midst of
0608: * traversing table right now.)
0609: */
0610:
0611: for (int i = 0; i < oldCapacity; i++) {
0612: // We need to guarantee that any existing reads of old Map can
0613: // proceed. So we cannot yet null out each bin.
0614: Entry e = oldTable[i];
0615:
0616: if (e != null) {
0617: int idx = e.hash & mask;
0618: Entry next = e.next;
0619:
0620: // Single node on list
0621: if (next == null) {
0622: newTable[idx] = e;
0623: } else {
0624: // Reuse trailing consecutive sequence of all same bit
0625: Entry lastRun = e;
0626: int lastIdx = idx;
0627: for (Entry last = next; last != null; last = last.next) {
0628: int k = last.hash & mask;
0629: if (k != lastIdx) {
0630: lastIdx = k;
0631: lastRun = last;
0632: }
0633: }
0634: newTable[lastIdx] = lastRun;
0635:
0636: // Clone all remaining nodes
0637: for (Entry p = e; p != lastRun; p = p.next) {
0638: int k = p.hash & mask;
0639: newTable[k] = new Entry(p.hash, p.key, p.value,
0640: newTable[k]);
0641: }
0642: }
0643: }
0644: }
0645:
0646: table = newTable;
0647: }
0648:
0649: /**
0650: * Removes the key (and its corresponding value) from this table. This
0651: * method does nothing if the key is not in the table.
0652: *
0653: * @param key
0654: * the key that needs to be removed.
0655: * @return the value to which the key had been mapped in this table, or
0656: * <code>null</code> if the key did not have a mapping.
0657: * @exception NullPointerException
0658: * if the key is <code>null</code>.
0659: */
0660: public Object remove(Object key) {
0661: return remove(key, null);
0662: }
0663:
0664: /**
0665: * Removes the (key, value) pair from this table. This method does nothing
0666: * if the key is not in the table, or if the key is associated with a
0667: * different value. This method is needed by EntrySet.
0668: *
0669: * @param key
0670: * the key that needs to be removed.
0671: * @param value
0672: * the associated value. If the value is null, it means "any
0673: * value".
0674: * @return the value to which the key had been mapped in this table, or
0675: * <code>null</code> if the key did not have a mapping.
0676: * @exception NullPointerException
0677: * if the key is <code>null</code>.
0678: */
0679: protected Object remove(Object key, Object value) {
0680: /*
0681: * Find the entry, then 1. Set value field to null, to force get() to
0682: * retry 2. Rebuild the list without this entry. All entries following
0683: * removed node can stay in list, but all preceeding ones need to be
0684: * cloned. Traversals rely on this strategy to ensure that elements will
0685: * not be repeated during iteration.
0686: */
0687:
0688: int hash = hash(key);
0689: Segment seg = segments[hash & SEGMENT_MASK];
0690:
0691: synchronized (seg) {
0692: Entry[] tab = table;
0693: int index = hash & (tab.length - 1);
0694: Entry first = tab[index];
0695: Entry e = first;
0696:
0697: for (;;) {
0698: if (e == null) {
0699: return null;
0700: }
0701: if (e.hash == hash && eq(key, e.key)) {
0702: break;
0703: }
0704: e = e.next;
0705: }
0706:
0707: Object oldValue = e.value;
0708: if (value != null && !value.equals(oldValue)) {
0709: return null;
0710: }
0711:
0712: e.value = null;
0713:
0714: Entry head = e.next;
0715: for (Entry p = first; p != e; p = p.next) {
0716: head = new Entry(p.hash, p.key, p.value, head);
0717: }
0718: tab[index] = head;
0719: seg.count--;
0720: return oldValue;
0721: }
0722: }
0723:
0724: /**
0725: * Returns <tt>true</tt> if this map maps one or more keys to the
0726: * specified value. Note: This method requires a full internal traversal of
0727: * the hash table, and so is much slower than method <tt>containsKey</tt>.
0728: *
0729: * @param value
0730: * value whose presence in this map is to be tested.
0731: * @return <tt>true</tt> if this map maps one or more keys to the
0732: * specified value.
0733: * @exception NullPointerException
0734: * if the value is <code>null</code>.
0735: */
0736: public boolean containsValue(Object value) {
0737: if (value == null) {
0738: throw new IllegalArgumentException("Value must not be null");
0739: }
0740: for (int s = 0; s < segments.length; ++s) {
0741: Segment seg = segments[s];
0742: Entry[] tab;
0743: synchronized (seg) {
0744: tab = table;
0745: }
0746: for (int i = s; i < tab.length; i += segments.length) {
0747: for (Entry e = tab[i]; e != null; e = e.next) {
0748: if (value.equals(e.value)) {
0749: return true;
0750: }
0751: }
0752: }
0753: }
0754: return false;
0755: }
0756:
0757: /**
0758: * Tests if some key maps into the specified value in this table. This
0759: * operation is more expensive than the <code>containsKey</code> method.
0760: * <p>
0761: *
0762: * Note that this method is identical in functionality to containsValue,
0763: * (which is part of the Map interface in the collections framework).
0764: *
0765: * @param value
0766: * a value to search for.
0767: * @return <code>true</code> if and only if some key maps to the
0768: * <code>value</code> argument in this table as determined by the
0769: * <tt>equals</tt> method; <code>false</code> otherwise.
0770: * @exception NullPointerException
0771: * if the value is <code>null</code>.
0772: * @see #containsKey(Object)
0773: * @see #containsValue(Object)
0774: * @see Map
0775: */
0776: public boolean contains(Object value) {
0777: return containsValue(value);
0778: }
0779:
0780: /**
0781: * Copies all of the mappings from the specified map to this one.
0782: *
0783: * These mappings replace any mappings that this map had for any of the keys
0784: * currently in the specified Map.
0785: *
0786: * @param t
0787: * Mappings to be stored in this map.
0788: */
0789: public void putAll(Map t) {
0790: int n = t.size();
0791: if (n == 0) {
0792: return;
0793: }
0794:
0795: // Expand enough to hold at least n elements without resizing.
0796: // We can only resize table by factor of two at a time.
0797: // It is faster to rehash with fewer elements, so do it now.
0798: for (;;) {
0799: Entry[] tab;
0800: int max;
0801: synchronized (segments[0]) { // must synch on some segment. pick 0.
0802: tab = table;
0803: max = threshold * CONCURRENCY_LEVEL;
0804: }
0805: if (n < max) {
0806: break;
0807: }
0808: resize(0, tab);
0809: }
0810:
0811: for (Iterator it = t.entrySet().iterator(); it.hasNext();) {
0812: Map.Entry entry = (Map.Entry) it.next();
0813: put(entry.getKey(), entry.getValue());
0814: }
0815: }
0816:
0817: /**
0818: * Removes all mappings from this map.
0819: */
0820: public void clear() {
0821: // We don't need all locks at once so long as locks
0822: // are obtained in low to high order
0823: for (int s = 0; s < segments.length; ++s) {
0824: Segment seg = segments[s];
0825: synchronized (seg) {
0826: Entry[] tab = table;
0827: for (int i = s; i < tab.length; i += segments.length) {
0828: for (Entry e = tab[i]; e != null; e = e.next) {
0829: e.value = null;
0830: }
0831: tab[i] = null;
0832: seg.count = 0;
0833: }
0834: }
0835: }
0836: }
0837:
0838: /**
0839: * Returns a shallow copy of this <tt>ConcurrentHashMap</tt> instance: the
0840: * keys and values themselves are not cloned.
0841: *
0842: * @return a shallow copy of this map.
0843: */
0844: public Object clone() {
0845: // We cannot call super.clone, since it would share final segments
0846: // array,
0847: // and there's no way to reassign finals.
0848: return new ConcurrentHashMap(this );
0849: }
0850:
0851: // Views
0852:
0853: protected transient Set keySet = null;
0854: protected transient Set entrySet = null;
0855: protected transient Collection values = null;
0856:
0857: /**
0858: * Returns a set view of the keys contained in this map. The set is backed
0859: * by the map, so changes to the map are reflected in the set, and
0860: * vice-versa. The set supports element removal, which removes the
0861: * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
0862: * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
0863: * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
0864: * <tt>addAll</tt> operations.
0865: *
0866: * @return a set view of the keys contained in this map.
0867: */
0868: public Set keySet() {
0869: Set ks = keySet;
0870: return (ks != null) ? ks : (keySet = new KeySet());
0871: }
0872:
0873: private class KeySet extends AbstractSet {
0874: /**
0875: * @see java.util.Set#iterator()
0876: */
0877: public Iterator iterator() {
0878: return new KeyIterator();
0879: }
0880:
0881: /**
0882: * @see java.util.Set#size()
0883: */
0884: public int size() {
0885: return ConcurrentHashMap.this .size();
0886: }
0887:
0888: /**
0889: * @see java.util.Set#contains(java.lang.Object)
0890: */
0891: public boolean contains(Object o) {
0892: return ConcurrentHashMap.this .containsKey(o);
0893: }
0894:
0895: /**
0896: * @see java.util.Set#remove(java.lang.Object)
0897: */
0898: public boolean remove(Object o) {
0899: return ConcurrentHashMap.this .remove(o) != null;
0900: }
0901:
0902: /**
0903: * @see java.util.Set#clear()
0904: */
0905: public void clear() {
0906: ConcurrentHashMap.this .clear();
0907: }
0908: }
0909:
0910: /**
0911: * Returns a collection view of the values contained in this map. The
0912: * collection is backed by the map, so changes to the map are reflected in
0913: * the collection, and vice-versa. The collection supports element removal,
0914: * which removes the corresponding mapping from this map, via the
0915: * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
0916: * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
0917: * operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
0918: * operations.
0919: *
0920: * @return a collection view of the values contained in this map.
0921: */
0922: public Collection values() {
0923: Collection vs = values;
0924: return (vs != null) ? vs : (values = new Values());
0925: }
0926:
0927: private class Values extends AbstractCollection {
0928: /**
0929: * @see java.util.AbstractCollection#iterator()
0930: */
0931: public Iterator iterator() {
0932: return new ValueIterator();
0933: }
0934:
0935: /**
0936: * @see java.util.AbstractCollection#size()
0937: */
0938: public int size() {
0939: return ConcurrentHashMap.this .size();
0940: }
0941:
0942: /**
0943: * @see java.util.AbstractCollection#contains(java.lang.Object)
0944: */
0945: public boolean contains(Object o) {
0946: return ConcurrentHashMap.this .containsValue(o);
0947: }
0948:
0949: /**
0950: * @see java.util.AbstractCollection#clear()
0951: */
0952: public void clear() {
0953: ConcurrentHashMap.this .clear();
0954: }
0955: }
0956:
0957: /**
0958: * Returns a collection view of the mappings contained in this map. Each
0959: * element in the returned collection is a <tt>Map.Entry</tt>. The
0960: * collection is backed by the map, so changes to the map are reflected in
0961: * the collection, and vice-versa. The collection supports element removal,
0962: * which removes the corresponding mapping from the map, via the
0963: * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
0964: * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
0965: * operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
0966: * operations.
0967: *
0968: * @return a collection view of the mappings contained in this map.
0969: */
0970: public Set entrySet() {
0971: Set es = entrySet;
0972: return (es != null) ? es : (entrySet = new EntrySet());
0973: }
0974:
0975: private class EntrySet extends AbstractSet {
0976: /**
0977: * @see java.util.Set#iterator()
0978: */
0979: public Iterator iterator() {
0980: return new HashIterator();
0981: }
0982:
0983: /**
0984: * @see java.util.Set#contains(java.lang.Object)
0985: */
0986: public boolean contains(Object o) {
0987: if (!(o instanceof Map.Entry)) {
0988: return false;
0989: }
0990: Map.Entry entry = (Map.Entry) o;
0991: Object v = ConcurrentHashMap.this .get(entry.getKey());
0992: return v != null && v.equals(entry.getValue());
0993: }
0994:
0995: /**
0996: * @see java.util.Set#remove(java.lang.Object)
0997: */
0998: public boolean remove(Object o) {
0999: if (!(o instanceof Map.Entry)) {
1000: return false;
1001: }
1002: Map.Entry e = (Map.Entry) o;
1003: return ConcurrentHashMap.this .remove(e.getKey(), e
1004: .getValue()) != null;
1005: }
1006:
1007: /**
1008: * @see java.util.Set#size()
1009: */
1010: public int size() {
1011: return ConcurrentHashMap.this .size();
1012: }
1013:
1014: /**
1015: * @see java.util.Set#clear()
1016: */
1017: public void clear() {
1018: ConcurrentHashMap.this .clear();
1019: }
1020: }
1021:
1022: /**
1023: * Returns an enumeration of the keys in this table.
1024: *
1025: * @return an enumeration of the keys in this table.
1026: * @see Enumeration
1027: * @see #elements()
1028: * @see #keySet()
1029: * @see Map
1030: */
1031: public Enumeration keys() {
1032: return new KeyIterator();
1033: }
1034:
1035: /**
1036: * Returns an enumeration of the values in this table. Use the Enumeration
1037: * methods on the returned object to fetch the elements sequentially.
1038: *
1039: * @return an enumeration of the values in this table.
1040: * @see java.util.Enumeration
1041: * @see #keys()
1042: * @see #values()
1043: * @see Map
1044: */
1045: public Enumeration elements() {
1046: return new ValueIterator();
1047: }
1048:
1049: /**
1050: * ConcurrentHashMap collision list entry.
1051: */
1052: protected static class Entry implements Map.Entry {
1053: /*
1054: * The use of volatile for value field ensures that we can detect status
1055: * changes without synchronization. The other fields are never changed,
1056: * and are marked as final.
1057: */
1058:
1059: protected final Object key;
1060: protected volatile Object value;
1061: protected final int hash;
1062: protected final Entry next;
1063:
1064: Entry(int hash, Object key, Object value, Entry next) {
1065: this .value = value;
1066: this .hash = hash;
1067: this .key = key;
1068: this .next = next;
1069: }
1070:
1071: // Map.Entry Ops
1072:
1073: /**
1074: * @see java.util.Map.Entry#getKey()
1075: */
1076: public Object getKey() {
1077: return key;
1078: }
1079:
1080: /**
1081: * Get the value. Note: In an entrySet or entrySet.iterator, unless you
1082: * can guarantee lack of concurrent modification,
1083: * <tt>getValue</tt> <em>might</em> return null, reflecting the fact
1084: * that the entry has been concurrently removed. However, there are no
1085: * assurances that concurrent removals will be reflected using this
1086: * method.
1087: *
1088: * @return the current value, or null if the entry has been detectably
1089: * removed.
1090: */
1091: public Object getValue() {
1092: return value;
1093: }
1094:
1095: /**
1096: * Set the value of this entry. Note: In an entrySet or
1097: * entrySet.iterator), unless you can guarantee lack of concurrent
1098: * modification, <tt>setValue</tt> is not strictly guaranteed to
1099: * actually replace the value field obtained via the <tt>get</tt>
1100: * operation of the underlying hash table in multithreaded applications.
1101: * If iterator-wide synchronization is not used, and any other
1102: * concurrent <tt>put</tt> or <tt>remove</tt> operations occur,
1103: * sometimes even to <em>other</em> entries, then this change is not
1104: * guaranteed to be reflected in the hash table. (It might, or it might
1105: * not. There are no assurances either way.)
1106: *
1107: * @param value
1108: * the new value.
1109: * @return the previous value, or null if entry has been detectably
1110: * removed.
1111: * @exception NullPointerException
1112: * if the value is <code>null</code>.
1113: *
1114: */
1115: public Object setValue(Object value) {
1116: if (value == null) {
1117: throw new IllegalArgumentException(
1118: "Value must not be null");
1119: }
1120: Object oldValue = this .value;
1121: this .value = value;
1122: return oldValue;
1123: }
1124:
1125: /**
1126: * @see java.util.Map.Entry#equals(java.lang.Object)
1127: */
1128: public boolean equals(Object o) {
1129: if (!(o instanceof Map.Entry)) {
1130: return false;
1131: }
1132: Map.Entry e = (Map.Entry) o;
1133: return (key.equals(e.getKey()) && value
1134: .equals(e.getValue()));
1135: }
1136:
1137: /**
1138: * @see java.util.Map.Entry#hashCode()
1139: */
1140: public int hashCode() {
1141: return key.hashCode() ^ value.hashCode();
1142: }
1143:
1144: /**
1145: * @see java.lang.Object#toString()
1146: */
1147: public String toString() {
1148: return key + "=" + value;
1149: }
1150: }
1151:
1152: protected class HashIterator implements Iterator, Enumeration {
1153: protected final Entry[] tab; // snapshot of table
1154: protected int index; // current slot
1155: protected Entry entry = null; // current node of slot
1156: protected Object currentKey; // key for current node
1157: protected Object currentValue; // value for current node
1158: protected Entry lastReturned = null; // last node returned by next
1159:
1160: protected HashIterator() {
1161: // force all segments to synch
1162: synchronized (segments[0]) {
1163: tab = table;
1164: }
1165: for (int i = 1; i < segments.length; ++i) {
1166: segments[i].synch();
1167: }
1168: index = tab.length - 1;
1169: }
1170:
1171: /**
1172: * @see java.util.Enumeration#hasMoreElements()
1173: */
1174: public boolean hasMoreElements() {
1175: return hasNext();
1176: }
1177:
1178: /**
1179: * @see java.util.Enumeration#nextElement()
1180: */
1181: public Object nextElement() {
1182: return next();
1183: }
1184:
1185: /**
1186: * @see java.util.Iterator#hasNext()
1187: */
1188: public boolean hasNext() {
1189: /*
1190: * currentkey and currentValue are set here to ensure that next()
1191: * returns normally if hasNext() returns true. This avoids surprises
1192: * especially when final element is removed during traversal --
1193: * instead, we just ignore the removal during current traversal.
1194: */
1195:
1196: for (;;) {
1197: if (entry != null) {
1198: Object v = entry.value;
1199: if (v != null) {
1200: currentKey = entry.key;
1201: currentValue = v;
1202: return true;
1203: } else {
1204: entry = entry.next;
1205: }
1206: }
1207:
1208: while (entry == null && index >= 0) {
1209: entry = tab[index--];
1210: }
1211:
1212: if (entry == null) {
1213: currentKey = currentValue = null;
1214: return false;
1215: }
1216: }
1217: }
1218:
1219: protected Object returnValueOfNext() {
1220: return entry;
1221: }
1222:
1223: /**
1224: * @see java.util.Iterator#next()
1225: */
1226: public Object next() {
1227: if (currentKey == null && !hasNext()) {
1228: throw new NoSuchElementException();
1229: }
1230:
1231: Object result = returnValueOfNext();
1232: lastReturned = entry;
1233: currentKey = currentValue = null;
1234: entry = entry.next;
1235: return result;
1236: }
1237:
1238: /**
1239: * @see java.util.Iterator#remove()
1240: */
1241: public void remove() {
1242: if (lastReturned == null) {
1243: throw new IllegalStateException();
1244: }
1245: ConcurrentHashMap.this .remove(lastReturned.key);
1246: lastReturned = null;
1247: }
1248: }
1249:
1250: protected class KeyIterator extends HashIterator {
1251: protected Object returnValueOfNext() {
1252: return currentKey;
1253: }
1254: }
1255:
1256: protected class ValueIterator extends HashIterator {
1257: protected Object returnValueOfNext() {
1258: return currentValue;
1259: }
1260: }
1261:
1262: /**
1263: * Save the state of the <tt>ConcurrentHashMap</tt> instance to a stream
1264: * (i.e., serialize it).
1265: * @param s
1266: * @throws IOException
1267: *
1268: * @serialData An estimate of the table size, followed by the key (Object)
1269: * and value (Object) for each key-value mapping, followed by a
1270: * null pair. The key-value mappings are emitted in no
1271: * particular order.
1272: */
1273: private void writeObject(java.io.ObjectOutputStream s)
1274: throws IOException {
1275: // Write out the loadfactor, and any hidden stuff
1276: s.defaultWriteObject();
1277:
1278: // Write out capacity estimate. It is OK if this
1279: // changes during the write, since it is only used by
1280: // readObject to set initial capacity, to avoid needless resizings.
1281:
1282: int cap;
1283: synchronized (segments[0]) {
1284: cap = table.length;
1285: }
1286: s.writeInt(cap);
1287:
1288: // Write out keys and values (alternating)
1289: for (int k = 0; k < segments.length; ++k) {
1290: Segment seg = segments[k];
1291: Entry[] tab;
1292: synchronized (seg) {
1293: tab = table;
1294: }
1295: for (int i = k; i < tab.length; i += segments.length) {
1296: for (Entry e = tab[i]; e != null; e = e.next) {
1297: s.writeObject(e.key);
1298: s.writeObject(e.value);
1299: }
1300: }
1301: }
1302:
1303: s.writeObject(null);
1304: s.writeObject(null);
1305: }
1306:
1307: /**
1308: * Reconstitute the <tt>ConcurrentHashMap</tt> instance from a stream
1309: * (i.e., deserialize it).
1310: * @param s
1311: * @throws IOException
1312: * @throws ClassNotFoundException
1313: */
1314: private void readObject(java.io.ObjectInputStream s)
1315: throws IOException, ClassNotFoundException {
1316: // Read in the threshold, loadfactor, and any hidden stuff
1317: s.defaultReadObject();
1318:
1319: int cap = s.readInt();
1320: table = newTable(cap);
1321: for (int i = 0; i < segments.length; ++i) {
1322: segments[i] = new Segment();
1323: }
1324:
1325: // Read the keys and values, and put the mappings in the table
1326: for (;;) {
1327: Object key = s.readObject();
1328: Object value = s.readObject();
1329: if (key == null) {
1330: break;
1331: }
1332: put(key, value);
1333: }
1334: }
1335: }
|