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