+++ /dev/null
-/*
- File: ConcurrentHashMap
-
- Written by Doug Lea. Adapted and released, under explicit
- permission, from JDK1.2 HashMap.java and Hashtable.java which
- carries the following copyright:
-
- * Copyright 1997 by Sun Microsystems, Inc.,
- * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
- * All rights reserved.
- *
- * This software is the confidential and proprietary information
- * of Sun Microsystems, Inc. ("Confidential Information"). You
- * shall not disclose such Confidential Information and shall use
- * it only in accordance with the terms of the license agreement
- * you entered into with Sun.
-
- History:
- Date Who What
- 26nov2000 dl Created, based on ConcurrentReaderHashMap
- 12jan2001 dl public release
- 17nov2001 dl Minor tunings
- 24oct2003 dl Segment implements Serializable
-*/
-
-package EDU.oswego.cs.dl.util.concurrent;
-
-import java.util.Map;
-import java.util.AbstractMap;
-import java.util.AbstractSet;
-import java.util.AbstractCollection;
-import java.util.Collection;
-import java.util.Set;
-import java.util.Iterator;
-import java.util.Enumeration;
-import java.util.NoSuchElementException;
-
-import java.io.Serializable;
-import java.io.IOException;
-import java.io.ObjectInputStream;
-import java.io.ObjectOutputStream;
-
-
-/**
- * A version of Hashtable supporting
- * concurrency for both retrievals and updates:
- *
- * <dl>
- * <dt> Retrievals
- *
- * <dd> Retrievals may overlap updates. (This is the same policy as
- * ConcurrentReaderHashMap.) Successful retrievals using get(key) and
- * containsKey(key) usually run without locking. Unsuccessful
- * retrievals (i.e., when the key is not present) do involve brief
- * synchronization (locking). Because retrieval operations can
- * ordinarily overlap with update operations (i.e., put, remove, and
- * their derivatives), retrievals can only be guaranteed to return the
- * results of the most recently <em>completed</em> operations holding
- * upon their onset. Retrieval operations may or may not return
- * results reflecting in-progress writing operations. However, the
- * retrieval operations do always return consistent results -- either
- * those holding before any single modification or after it, but never
- * a nonsense result. For aggregate operations such as putAll and
- * clear, concurrent reads may reflect insertion or removal of only
- * some entries.
- * <p>
- *
- * Iterators and Enumerations (i.e., those returned by
- * keySet().iterator(), entrySet().iterator(), values().iterator(),
- * keys(), and elements()) return elements reflecting the state of the
- * hash table at some point at or since the creation of the
- * iterator/enumeration. They will return at most one instance of
- * each element (via next()/nextElement()), but might or might not
- * reflect puts and removes that have been processed since they were
- * created. They do <em>not</em> throw ConcurrentModificationException.
- * However, these iterators are designed to be used by only one
- * thread at a time. Passing an iterator across multiple threads may
- * lead to unpredictable results if the table is being concurrently
- * modified. <p>
- *
- *
- * <dt> Updates
- *
- * <dd> This class supports a hard-wired preset <em>concurrency
- * level</em> of 32. This allows a maximum of 32 put and/or remove
- * operations to proceed concurrently. This level is an upper bound on
- * concurrency, not a guarantee, since it interacts with how
- * well-strewn elements are across bins of the table. (The preset
- * value in part reflects the fact that even on large multiprocessors,
- * factors other than synchronization tend to be bottlenecks when more
- * than 32 threads concurrently attempt updates.)
- * Additionally, operations triggering internal resizing and clearing
- * do not execute concurrently with any operation.
- * <p>
- *
- * There is <em>NOT</em> any support for locking the entire table to
- * prevent updates. This makes it imposssible, for example, to
- * add an element only if it is not already present, since another
- * thread may be in the process of doing the same thing.
- * If you need such capabilities, consider instead using the
- * ConcurrentReaderHashMap class.
- *
- * </dl>
- *
- * Because of how concurrency control is split up, the
- * size() and isEmpty() methods require accumulations across 32
- * control segments, and so might be slightly slower than you expect.
- * <p>
- *
- * This class may be used as a direct replacement for
- * java.util.Hashtable in any application that does not rely
- * on the ability to lock the entire table to prevent updates.
- * As of this writing, it performs much faster than Hashtable in
- * typical multi-threaded applications with multiple readers and writers.
- * Like Hashtable but unlike java.util.HashMap,
- * this class does NOT allow <tt>null</tt> to be used as a key or
- * value.
- * <p>
- *
- * Implementation note: A slightly
- * faster implementation of this class will be possible once planned
- * Java Memory Model revisions are in place.
- *
- * <p>[<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>]
-
- **/
-
-
-public class ConcurrentHashMap
- extends AbstractMap
- implements Map, Cloneable, Serializable {
-
- /*
- The basic strategy is an optimistic-style scheme based on
- the guarantee that the hash table and its lists are always
- kept in a consistent enough state to be read without locking:
-
- * Read operations first proceed without locking, by traversing the
- apparently correct list of the apparently correct bin. If an
- entry is found, but not invalidated (value field null), it is
- returned. If not found, operations must recheck (after a memory
- barrier) to make sure they are using both the right list and
- the right table (which can change under resizes). If
- invalidated, reads must acquire main update lock to wait out
- the update, and then re-traverse.
-
- * All list additions are at the front of each bin, making it easy
- to check changes, and also fast to traverse. Entry next
- pointers are never assigned. Remove() builds new nodes when
- necessary to preserve this.
-
- * Remove() (also clear()) invalidates removed nodes to alert read
- operations that they must wait out the full modifications.
-
- * Locking for puts, removes (and, when necessary gets, etc)
- is controlled by Segments, each covering a portion of the
- table. During operations requiring global exclusivity (mainly
- resize and clear), ALL of these locks are acquired at once.
- Note that these segments are NOT contiguous -- they are based
- on the least 5 bits of hashcodes. This ensures that the same
- segment controls the same slots before and after resizing, which
- is necessary for supporting concurrent retrievals. This
- comes at the price of a mismatch of logical vs physical locality,
- but this seems not to be a performance problem in practice.
-
- */
-
- /**
- * The hash table data.
- */
- protected transient Entry[] table;
-
-
- /**
- * The number of concurrency control segments.
- * The value can be at most 32 since ints are used
- * as bitsets over segments. Emprically, it doesn't
- * seem to pay to decrease it either, so the value should be at least 32.
- * In other words, do not redefine this :-)
- **/
-
- protected static final int CONCURRENCY_LEVEL = 32;
-
- /**
- * Mask value for indexing into segments
- **/
-
- protected static final int SEGMENT_MASK = CONCURRENCY_LEVEL - 1;
-
- /**
- * Bookkeeping for each concurrency control segment.
- * Each segment contains a local count of the number of
- * elements in its region.
- * However, the main use of a Segment is for its lock.
- **/
- protected final static class Segment implements Serializable {
- /**
- * The number of elements in this segment's region.
- * It is always updated within synchronized blocks.
- **/
- protected int count;
-
- /**
- * Get the count under synch.
- **/
- protected synchronized int getCount() { return count; }
-
- /**
- * Force a synchronization
- **/
- protected synchronized void synch() {}
- }
-
- /**
- * The array of concurrency control segments.
- **/
-
- protected final Segment[] segments = new Segment[CONCURRENCY_LEVEL];
-
-
- /**
- * The default initial number of table slots for this table (32).
- * Used when not otherwise specified in constructor.
- **/
- public static int DEFAULT_INITIAL_CAPACITY = 32;
-
-
- /**
- * The minimum capacity, used if a lower value is implicitly specified
- * by either of the constructors with arguments.
- * MUST be a power of two.
- */
- private static final int MINIMUM_CAPACITY = 32;
-
- /**
- * The maximum capacity, used if a higher value is implicitly specified
- * by either of the constructors with arguments.
- * MUST be a power of two <= 1<<30.
- */
- private static final int MAXIMUM_CAPACITY = 1 << 30;
-
- /**
- * The default load factor for this table (0.75)
- * Used when not otherwise specified in constructor.
- **/
-
- public static final float DEFAULT_LOAD_FACTOR = 0.75f;
-
- /**
- * The load factor for the hash table.
- *
- * @serial
- */
- protected final float loadFactor;
-
- /**
- * Per-segment resize threshold.
- *
- * @serial
- */
- protected int threshold;
-
-
- /**
- * Number of segments voting for resize. The table is
- * doubled when 1/4 of the segments reach threshold.
- * Volatile but updated without synch since this is just a heuristic.
- **/
-
- protected transient volatile int votesForResize;
-
-
- /**
- * Return the number of set bits in w.
- * For a derivation of this algorithm, see
- * "Algorithms and data structures with applications to
- * graphics and geometry", by Jurg Nievergelt and Klaus Hinrichs,
- * Prentice Hall, 1993.
- * See also notes by Torsten Sillke at
- * http://www.mathematik.uni-bielefeld.de/~sillke/PROBLEMS/bitcount
- **/
- protected static int bitcount(int w) {
- w -= (0xaaaaaaaa & w) >>> 1;
- w = (w & 0x33333333) + ((w >>> 2) & 0x33333333);
- w = (w + (w >>> 4)) & 0x0f0f0f0f;
- w += w >>> 8;
- w += w >>> 16;
- return w & 0xff;
- }
-
- /**
- * Returns the appropriate capacity (power of two) for the specified
- * initial capacity argument.
- */
- private int p2capacity(int initialCapacity) {
- int cap = initialCapacity;
-
- // Compute the appropriate capacity
- int result;
- if (cap > MAXIMUM_CAPACITY || cap < 0) {
- result = MAXIMUM_CAPACITY;
- } else {
- result = MINIMUM_CAPACITY;
- while (result < cap)
- result <<= 1;
- }
- return result;
- }
-
- /**
- * Return hash code for Object x. Since we are using power-of-two
- * tables, it is worth the effort to improve hashcode via
- * the same multiplicative scheme as used in IdentityHashMap.
- */
- protected static int hash(Object x) {
- int h = x.hashCode();
- // Multiply by 127 (quickly, via shifts), and mix in some high
- // bits to help guard against bunching of codes that are
- // consecutive or equally spaced.
- return ((h << 7) - h + (h >>> 9) + (h >>> 17));
- }
-
-
- /**
- * Check for equality of non-null references x and y.
- **/
- protected boolean eq(Object x, Object y) {
- return x == y || x.equals(y);
- }
-
- /** Create table array and set the per-segment threshold **/
- protected Entry[] newTable(int capacity) {
- threshold = (int)(capacity * loadFactor / CONCURRENCY_LEVEL) + 1;
- return new Entry[capacity];
- }
-
- /**
- * Constructs a new, empty map with the specified initial
- * capacity and the specified load factor.
- *
- * @param initialCapacity the initial capacity.
- * The actual initial capacity is rounded to the nearest power of two.
- * @param loadFactor the load factor threshold, used to control resizing.
- * This value is used in an approximate way: When at least
- * a quarter of the segments of the table reach per-segment threshold, or
- * one of the segments itself exceeds overall threshold,
- * the table is doubled.
- * This will on average cause resizing when the table-wide
- * load factor is slightly less than the threshold. If you'd like
- * to avoid resizing, you can set this to a ridiculously large
- * value.
- * @throws IllegalArgumentException if the load factor is nonpositive.
- */
- public ConcurrentHashMap(int initialCapacity,
- float loadFactor) {
- if (!(loadFactor > 0))
- throw new IllegalArgumentException("Illegal Load factor: "+
- loadFactor);
- this.loadFactor = loadFactor;
- for (int i = 0; i < segments.length; ++i)
- segments[i] = new Segment();
- int cap = p2capacity(initialCapacity);
- table = newTable(cap);
- }
-
- /**
- * Constructs a new, empty map with the specified initial
- * capacity and default load factor.
- *
- * @param initialCapacity the initial capacity of the
- * ConcurrentHashMap.
- * @throws IllegalArgumentException if the initial maximum number
- * of elements is less
- * than zero.
- */
- public ConcurrentHashMap(int initialCapacity) {
- this(initialCapacity, DEFAULT_LOAD_FACTOR);
- }
-
- /**
- * Constructs a new, empty map with a default initial capacity
- * and default load factor.
- */
- public ConcurrentHashMap() {
- this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
- }
-
- /**
- * Constructs a new map with the same mappings as the given map. The
- * map is created with a capacity of twice the number of mappings in
- * the given map or 32 (whichever is greater), and a default load factor.
- */
- public ConcurrentHashMap(Map t) {
- this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1,
- MINIMUM_CAPACITY),
- DEFAULT_LOAD_FACTOR);
- putAll(t);
- }
-
- /**
- * Returns the number of key-value mappings in this map.
- *
- * @return the number of key-value mappings in this map.
- */
- public int size() {
- int c = 0;
- for (int i = 0; i < segments.length; ++i)
- c += segments[i].getCount();
- return c;
- }
-
- /**
- * Returns <tt>true</tt> if this map contains no key-value mappings.
- *
- * @return <tt>true</tt> if this map contains no key-value mappings.
- */
- public boolean isEmpty() {
- for (int i = 0; i < segments.length; ++i)
- if (segments[i].getCount() != 0)
- return false;
- return true;
- }
-
-
- /**
- * Returns the value to which the specified key is mapped in this table.
- *
- * @param key a key in the table.
- * @return the value to which the key is mapped in this table;
- * <code>null</code> if the key is not mapped to any value in
- * this table.
- * @exception NullPointerException if the key is
- * <code>null</code>.
- * @see #put(Object, Object)
- */
- public Object get(Object key) {
- int hash = hash(key); // throws null pointer exception if key null
-
- // Try first without locking...
- Entry[] tab = table;
- int index = hash & (tab.length - 1);
- Entry first = tab[index];
- Entry e;
-
- for (e = first; e != null; e = e.next) {
- if (e.hash == hash && eq(key, e.key)) {
- Object value = e.value;
- if (value != null)
- return value;
- else
- break;
- }
- }
-
- // Recheck under synch if key apparently not there or interference
- Segment seg = segments[hash & SEGMENT_MASK];
- synchronized(seg) {
- tab = table;
- index = hash & (tab.length - 1);
- Entry newFirst = tab[index];
- if (e != null || first != newFirst) {
- for (e = newFirst; e != null; e = e.next) {
- if (e.hash == hash && eq(key, e.key))
- return e.value;
- }
- }
- return null;
- }
- }
-
- /**
- * Tests if the specified object is a key in this table.
- *
- * @param key possible key.
- * @return <code>true</code> if and only if the specified object
- * is a key in this table, as determined by the
- * <tt>equals</tt> method; <code>false</code> otherwise.
- * @exception NullPointerException if the key is
- * <code>null</code>.
- * @see #contains(Object)
- */
-
- public boolean containsKey(Object key) {
- return get(key) != null;
- }
-
-
- /**
- * Maps the specified <code>key</code> to the specified
- * <code>value</code> in this table. Neither the key nor the
- * value can be <code>null</code>. (Note that this policy is
- * the same as for java.util.Hashtable, but unlike java.util.HashMap,
- * which does accept nulls as valid keys and values.)<p>
- *
- * The value can be retrieved by calling the <code>get</code> method
- * with a key that is equal to the original key.
- *
- * @param key the table key.
- * @param value the value.
- * @return the previous value of the specified key in this table,
- * or <code>null</code> if it did not have one.
- * @exception NullPointerException if the key or value is
- * <code>null</code>.
- * @see Object#equals(Object)
- * @see #get(Object)
- */
- public Object put(Object key, Object value) {
- if (value == null)
- throw new NullPointerException();
-
- int hash = hash(key);
- Segment seg = segments[hash & SEGMENT_MASK];
- int segcount;
- Entry[] tab;
- int votes;
-
- synchronized(seg) {
- tab = table;
- int index = hash & (tab.length-1);
- Entry first = tab[index];
-
- for (Entry e = first; e != null; e = e.next) {
- if (e.hash == hash && eq(key, e.key)) {
- Object oldValue = e.value;
- e.value = value;
- return oldValue;
- }
- }
-
- // Add to front of list
- Entry newEntry = new Entry(hash, key, value, first);
- tab[index] = newEntry;
-
- if ((segcount = ++seg.count) < threshold)
- return null;
-
- int bit = (1 << (hash & SEGMENT_MASK));
- votes = votesForResize;
- if ((votes & bit) == 0)
- votes = votesForResize |= bit;
- }
-
- // Attempt resize if 1/4 segs vote,
- // or if this seg itself reaches the overall threshold.
- // (The latter check is just a safeguard to avoid pathological cases.)
- if (bitcount(votes) >= CONCURRENCY_LEVEL / 4 ||
- segcount > (threshold * CONCURRENCY_LEVEL))
- resize(0, tab);
-
- return null;
- }
-
- /**
- * Gather all locks in order to call rehash, by
- * recursing within synch blocks for each segment index.
- * @param index the current segment. initially call value must be 0
- * @param assumedTab the state of table on first call to resize. If
- * this changes on any call, the attempt is aborted because the
- * table has already been resized by another thread.
- */
-
- protected void resize(int index, Entry[] assumedTab) {
- Segment seg = segments[index];
- synchronized(seg) {
- if (assumedTab == table) {
- int next = index+1;
- if (next < segments.length)
- resize(next, assumedTab);
- else
- rehash();
- }
- }
- }
-
- /**
- * Rehashes the contents of this map into a new table
- * with a larger capacity.
- */
- protected void rehash() {
- votesForResize = 0; // reset
-
- Entry[] oldTable = table;
- int oldCapacity = oldTable.length;
-
- if (oldCapacity >= MAXIMUM_CAPACITY) {
- threshold = Integer.MAX_VALUE; // avoid retriggering
- return;
- }
-
- int newCapacity = oldCapacity << 1;
- Entry[] newTable = newTable(newCapacity);
- int mask = newCapacity - 1;
-
- /*
- * Reclassify nodes in each list to new Map. Because we are
- * using power-of-two expansion, the elements from each bin
- * must either stay at same index, or move to
- * oldCapacity+index. We also eliminate unnecessary node
- * creation by catching cases where old nodes can be reused
- * because their next fields won't change. Statistically, at
- * the default threshhold, only about one-sixth of them need
- * cloning. (The nodes they replace will be garbage
- * collectable as soon as they are no longer referenced by any
- * reader thread that may be in the midst of traversing table
- * right now.)
- */
-
- for (int i = 0; i < oldCapacity ; i++) {
- // We need to guarantee that any existing reads of old Map can
- // proceed. So we cannot yet null out each bin.
- Entry e = oldTable[i];
-
- if (e != null) {
- int idx = e.hash & mask;
- Entry next = e.next;
-
- // Single node on list
- if (next == null)
- newTable[idx] = e;
-
- else {
- // Reuse trailing consecutive sequence of all same bit
- Entry lastRun = e;
- int lastIdx = idx;
- for (Entry last = next; last != null; last = last.next) {
- int k = last.hash & mask;
- if (k != lastIdx) {
- lastIdx = k;
- lastRun = last;
- }
- }
- newTable[lastIdx] = lastRun;
-
- // Clone all remaining nodes
- for (Entry p = e; p != lastRun; p = p.next) {
- int k = p.hash & mask;
- newTable[k] = new Entry(p.hash, p.key,
- p.value, newTable[k]);
- }
- }
- }
- }
-
- table = newTable;
- }
-
-
- /**
- * Removes the key (and its corresponding value) from this
- * table. This method does nothing if the key is not in the table.
- *
- * @param key the key that needs to be removed.
- * @return the value to which the key had been mapped in this table,
- * or <code>null</code> if the key did not have a mapping.
- * @exception NullPointerException if the key is
- * <code>null</code>.
- */
- public Object remove(Object key) {
- return remove(key, null);
- }
-
-
- /**
- * Removes the (key, value) pair from this
- * table. This method does nothing if the key is not in the table,
- * or if the key is associated with a different value. This method
- * is needed by EntrySet.
- *
- * @param key the key that needs to be removed.
- * @param value the associated value. If the value is null,
- * it means "any value".
- * @return the value to which the key had been mapped in this table,
- * or <code>null</code> if the key did not have a mapping.
- * @exception NullPointerException if the key is
- * <code>null</code>.
- */
-
- protected Object remove(Object key, Object value) {
- /*
- Find the entry, then
- 1. Set value field to null, to force get() to retry
- 2. Rebuild the list without this entry.
- All entries following removed node can stay in list, but
- all preceeding ones need to be cloned. Traversals rely
- on this strategy to ensure that elements will not be
- repeated during iteration.
- */
-
- int hash = hash(key);
- Segment seg = segments[hash & SEGMENT_MASK];
-
- synchronized(seg) {
- Entry[] tab = table;
- int index = hash & (tab.length-1);
- Entry first = tab[index];
- Entry e = first;
-
- for (;;) {
- if (e == null)
- return null;
- if (e.hash == hash && eq(key, e.key))
- break;
- e = e.next;
- }
-
- Object oldValue = e.value;
- if (value != null && !value.equals(oldValue))
- return null;
-
- e.value = null;
-
- Entry head = e.next;
- for (Entry p = first; p != e; p = p.next)
- head = new Entry(p.hash, p.key, p.value, head);
- tab[index] = head;
- seg.count--;
- return oldValue;
- }
- }
-
-
- /**
- * Returns <tt>true</tt> if this map maps one or more keys to the
- * specified value. Note: This method requires a full internal
- * traversal of the hash table, and so is much slower than
- * method <tt>containsKey</tt>.
- *
- * @param value value whose presence in this map is to be tested.
- * @return <tt>true</tt> if this map maps one or more keys to the
- * specified value.
- * @exception NullPointerException if the value is <code>null</code>.
- */
- public boolean containsValue(Object value) {
-
- if (value == null) throw new NullPointerException();
-
- for (int s = 0; s < segments.length; ++s) {
- Segment seg = segments[s];
- Entry[] tab;
- synchronized(seg) { tab = table; }
- for (int i = s; i < tab.length; i+= segments.length) {
- for (Entry e = tab[i]; e != null; e = e.next)
- if (value.equals(e.value))
- return true;
- }
- }
- return false;
- }
-
- /**
- * Tests if some key maps into the specified value in this table.
- * This operation is more expensive than the <code>containsKey</code>
- * method.<p>
- *
- * Note that this method is identical in functionality to containsValue,
- * (which is part of the Map interface in the collections framework).
- *
- * @param value a value to search for.
- * @return <code>true</code> if and only if some key maps to the
- * <code>value</code> argument in this table as
- * determined by the <tt>equals</tt> method;
- * <code>false</code> otherwise.
- * @exception NullPointerException if the value is <code>null</code>.
- * @see #containsKey(Object)
- * @see #containsValue(Object)
- * @see Map
- */
-
- public boolean contains(Object value) {
- return containsValue(value);
- }
-
- /**
- * Copies all of the mappings from the specified map to this one.
- *
- * These mappings replace any mappings that this map had for any of the
- * keys currently in the specified Map.
- *
- * @param t Mappings to be stored in this map.
- */
-
- public void putAll(Map t) {
- int n = t.size();
- if (n == 0)
- return;
-
- // Expand enough to hold at least n elements without resizing.
- // We can only resize table by factor of two at a time.
- // It is faster to rehash with fewer elements, so do it now.
- for(;;) {
- Entry[] tab;
- int max;
- synchronized(segments[0]) { // must synch on some segment. pick 0.
- tab = table;
- max = threshold * CONCURRENCY_LEVEL;
- }
- if (n < max)
- break;
- resize(0, tab);
- }
-
- for (Iterator it = t.entrySet().iterator(); it.hasNext();) {
- Map.Entry entry = (Map.Entry) it.next();
- put(entry.getKey(), entry.getValue());
- }
- }
-
- /**
- * Removes all mappings from this map.
- */
-
- public void clear() {
- // We don't need all locks at once so long as locks
- // are obtained in low to high order
- for (int s = 0; s < segments.length; ++s) {
- Segment seg = segments[s];
- synchronized(seg) {
- Entry[] tab = table;
- for (int i = s; i < tab.length; i+= segments.length) {
- for (Entry e = tab[i]; e != null; e = e.next)
- e.value = null;
- tab[i] = null;
- seg.count = 0;
- }
- }
- }
- }
-
- /**
- * Returns a shallow copy of this
- * <tt>ConcurrentHashMap</tt> instance: the keys and
- * values themselves are not cloned.
- *
- * @return a shallow copy of this map.
- */
-
- public Object clone() {
- // We cannot call super.clone, since it would share final segments array,
- // and there's no way to reassign finals.
- return new ConcurrentHashMap(this);
- }
-
- // Views
-
- protected transient Set keySet = null;
- protected transient Set entrySet = null;
- protected transient Collection values = null;
-
- /**
- * Returns a set view of the keys contained in this map. The set is
- * backed by the map, so changes to the map are reflected in the set, and
- * vice-versa. The set supports element removal, which removes the
- * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
- * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
- * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
- * <tt>addAll</tt> operations.
- *
- * @return a set view of the keys contained in this map.
- */
-
- public Set keySet() {
- Set ks = keySet;
- return (ks != null)? ks : (keySet = new KeySet());
- }
-
- private class KeySet extends AbstractSet {
- public Iterator iterator() {
- return new KeyIterator();
- }
- public int size() {
- return ConcurrentHashMap.this.size();
- }
- public boolean contains(Object o) {
- return ConcurrentHashMap.this.containsKey(o);
- }
- public boolean remove(Object o) {
- return ConcurrentHashMap.this.remove(o) != null;
- }
- public void clear() {
- ConcurrentHashMap.this.clear();
- }
- }
-
- /**
- * Returns a collection view of the values contained in this map. The
- * collection is backed by the map, so changes to the map are reflected in
- * the collection, and vice-versa. The collection supports element
- * removal, which removes the corresponding mapping from this map, via the
- * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
- * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
- * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
- *
- * @return a collection view of the values contained in this map.
- */
-
- public Collection values() {
- Collection vs = values;
- return (vs != null)? vs : (values = new Values());
- }
-
- private class Values extends AbstractCollection {
- public Iterator iterator() {
- return new ValueIterator();
- }
- public int size() {
- return ConcurrentHashMap.this.size();
- }
- public boolean contains(Object o) {
- return ConcurrentHashMap.this.containsValue(o);
- }
- public void clear() {
- ConcurrentHashMap.this.clear();
- }
- }
-
- /**
- * Returns a collection view of the mappings contained in this map. Each
- * element in the returned collection is a <tt>Map.Entry</tt>. The
- * collection is backed by the map, so changes to the map are reflected in
- * the collection, and vice-versa. The collection supports element
- * removal, which removes the corresponding mapping from the map, via the
- * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
- * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
- * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
- *
- * @return a collection view of the mappings contained in this map.
- */
-
- public Set entrySet() {
- Set es = entrySet;
- return (es != null) ? es : (entrySet = new EntrySet());
- }
-
- private class EntrySet extends AbstractSet {
- public Iterator iterator() {
- return new HashIterator();
- }
- public boolean contains(Object o) {
- if (!(o instanceof Map.Entry))
- return false;
- Map.Entry entry = (Map.Entry)o;
- Object v = ConcurrentHashMap.this.get(entry.getKey());
- return v != null && v.equals(entry.getValue());
- }
- public boolean remove(Object o) {
- if (!(o instanceof Map.Entry))
- return false;
- Map.Entry e = (Map.Entry)o;
- return ConcurrentHashMap.this.remove(e.getKey(), e.getValue()) != null;
- }
- public int size() {
- return ConcurrentHashMap.this.size();
- }
- public void clear() {
- ConcurrentHashMap.this.clear();
- }
- }
-
- /**
- * Returns an enumeration of the keys in this table.
- *
- * @return an enumeration of the keys in this table.
- * @see Enumeration
- * @see #elements()
- * @see #keySet()
- * @see Map
- */
- public Enumeration keys() {
- return new KeyIterator();
- }
-
- /**
- * Returns an enumeration of the values in this table.
- * Use the Enumeration methods on the returned object to fetch the elements
- * sequentially.
- *
- * @return an enumeration of the values in this table.
- * @see java.util.Enumeration
- * @see #keys()
- * @see #values()
- * @see Map
- */
-
- public Enumeration elements() {
- return new ValueIterator();
- }
-
- /**
- * ConcurrentHashMap collision list entry.
- */
-
- protected static class Entry implements Map.Entry {
- /*
- The use of volatile for value field ensures that
- we can detect status changes without synchronization.
- The other fields are never changed, and are
- marked as final.
- */
-
- protected final Object key;
- protected volatile Object value;
- protected final int hash;
- protected final Entry next;
-
- Entry(int hash, Object key, Object value, Entry next) {
- this.value = value;
- this.hash = hash;
- this.key = key;
- this.next = next;
- }
-
- // Map.Entry Ops
-
- public Object getKey() {
- return key;
- }
-
- /**
- * Get the value. Note: In an entrySet or entrySet.iterator,
- * unless you can guarantee lack of concurrent modification,
- * <tt>getValue</tt> <em>might</em> return null, reflecting the
- * fact that the entry has been concurrently removed. However,
- * there are no assurances that concurrent removals will be
- * reflected using this method.
- *
- * @return the current value, or null if the entry has been
- * detectably removed.
- **/
- public Object getValue() {
- return value;
- }
-
- /**
- * Set the value of this entry. Note: In an entrySet or
- * entrySet.iterator), unless you can guarantee lack of concurrent
- * modification, <tt>setValue</tt> is not strictly guaranteed to
- * actually replace the value field obtained via the <tt>get</tt>
- * operation of the underlying hash table in multithreaded
- * applications. If iterator-wide synchronization is not used,
- * and any other concurrent <tt>put</tt> or <tt>remove</tt>
- * operations occur, sometimes even to <em>other</em> entries,
- * then this change is not guaranteed to be reflected in the hash
- * table. (It might, or it might not. There are no assurances
- * either way.)
- *
- * @param value the new value.
- * @return the previous value, or null if entry has been detectably
- * removed.
- * @exception NullPointerException if the value is <code>null</code>.
- *
- **/
-
- public Object setValue(Object value) {
- if (value == null)
- throw new NullPointerException();
- Object oldValue = this.value;
- this.value = value;
- return oldValue;
- }
-
- public boolean equals(Object o) {
- if (!(o instanceof Map.Entry))
- return false;
- Map.Entry e = (Map.Entry)o;
- return (key.equals(e.getKey()) && value.equals(e.getValue()));
- }
-
- public int hashCode() {
- return key.hashCode() ^ value.hashCode();
- }
-
- public String toString() {
- return key + "=" + value;
- }
-
- }
-
- protected class HashIterator implements Iterator, Enumeration {
- protected final Entry[] tab; // snapshot of table
- protected int index; // current slot
- protected Entry entry = null; // current node of slot
- protected Object currentKey; // key for current node
- protected Object currentValue; // value for current node
- protected Entry lastReturned = null; // last node returned by next
-
- protected HashIterator() {
- // force all segments to synch
- synchronized(segments[0]) { tab = table; }
- for (int i = 1; i < segments.length; ++i) segments[i].synch();
- index = tab.length - 1;
- }
-
- public boolean hasMoreElements() { return hasNext(); }
- public Object nextElement() { return next(); }
-
- public boolean hasNext() {
- /*
- currentkey and currentValue are set here to ensure that next()
- returns normally if hasNext() returns true. This avoids
- surprises especially when final element is removed during
- traversal -- instead, we just ignore the removal during
- current traversal.
- */
-
- for (;;) {
- if (entry != null) {
- Object v = entry.value;
- if (v != null) {
- currentKey = entry.key;
- currentValue = v;
- return true;
- }
- else
- entry = entry.next;
- }
-
- while (entry == null && index >= 0)
- entry = tab[index--];
-
- if (entry == null) {
- currentKey = currentValue = null;
- return false;
- }
- }
- }
-
- protected Object returnValueOfNext() { return entry; }
-
- public Object next() {
- if (currentKey == null && !hasNext())
- throw new NoSuchElementException();
-
- Object result = returnValueOfNext();
- lastReturned = entry;
- currentKey = currentValue = null;
- entry = entry.next;
- return result;
- }
-
- public void remove() {
- if (lastReturned == null)
- throw new IllegalStateException();
- ConcurrentHashMap.this.remove(lastReturned.key);
- lastReturned = null;
- }
-
- }
-
- protected class KeyIterator extends HashIterator {
- protected Object returnValueOfNext() { return currentKey; }
- }
-
- protected class ValueIterator extends HashIterator {
- protected Object returnValueOfNext() { return currentValue; }
- }
-
- /**
- * Save the state of the <tt>ConcurrentHashMap</tt>
- * instance to a stream (i.e.,
- * serialize it).
- *
- * @serialData
- * An estimate of the table size, followed by
- * the key (Object) and value (Object)
- * for each key-value mapping, followed by a null pair.
- * The key-value mappings are emitted in no particular order.
- */
-
- private void writeObject(java.io.ObjectOutputStream s)
- throws IOException {
- // Write out the loadfactor, and any hidden stuff
- s.defaultWriteObject();
-
- // Write out capacity estimate. It is OK if this
- // changes during the write, since it is only used by
- // readObject to set initial capacity, to avoid needless resizings.
-
- int cap;
- synchronized(segments[0]) { cap = table.length; }
- s.writeInt(cap);
-
- // Write out keys and values (alternating)
- for (int k = 0; k < segments.length; ++k) {
- Segment seg = segments[k];
- Entry[] tab;
- synchronized(seg) { tab = table; }
- for (int i = k; i < tab.length; i+= segments.length) {
- for (Entry e = tab[i]; e != null; e = e.next) {
- s.writeObject(e.key);
- s.writeObject(e.value);
- }
- }
- }
-
- s.writeObject(null);
- s.writeObject(null);
- }
-
- /**
- * Reconstitute the <tt>ConcurrentHashMap</tt>
- * instance from a stream (i.e.,
- * deserialize it).
- */
- private void readObject(java.io.ObjectInputStream s)
- throws IOException, ClassNotFoundException {
- // Read in the threshold, loadfactor, and any hidden stuff
- s.defaultReadObject();
-
- int cap = s.readInt();
- table = newTable(cap);
- for (int i = 0; i < segments.length; ++i)
- segments[i] = new Segment();
-
-
- // Read the keys and values, and put the mappings in the table
- for (;;) {
- Object key = s.readObject();
- Object value = s.readObject();
- if (key == null)
- break;
- put(key, value);
- }
- }
-}
projects / cdsspec-compiler.git / blobdiff