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