blitz_stable: src/EDU/oswego/cs/dl/util/concurrent/ConcurrentHashMap.java comparison

comparison src/EDU/oswego/cs/dl/util/concurrent/ConcurrentHashMap.java @ 0:3dc0c5604566

Initial checkin of blitz 2.0 fcs - no installer yet.

author	Dan Creswell <dan.creswell@gmail.com>
date	Sat, 21 Mar 2009 11:00:06 +0000
parents
children

comparison

equal deleted inserted replaced

--1:000000000000
+:3dc0c5604566
+/*
+File: ConcurrentHashMap
+Written by Doug Lea. Adapted 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
+*/
+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 {
+/**
+* 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);
+}
+}
+}

Mercurial > hg > blitz_stable

comparison src/EDU/oswego/cs/dl/util/concurrent/ConcurrentHashMap.java @ 0:3dc0c5604566