--- jsr166/src/extra166y/CustomConcurrentHashMap.java 2010/11/13 05:59:24 1.16 +++ jsr166/src/extra166y/CustomConcurrentHashMap.java 2015/09/13 16:28:13 1.37 @@ -1,10 +1,11 @@ /* * Written by Doug Lea with assistance from members of JCP JSR-166 * Expert Group and released to the public domain, as explained at - * http://creativecommons.org/licenses/publicdomain + * http://creativecommons.org/publicdomain/zero/1.0/ */ package extra166y; + import java.lang.ref.*; import java.lang.reflect.*; import java.io.*; @@ -19,22 +20,22 @@ import sun.misc.Unsafe; * user-supplied computational methods for setting and updating * values. In particular: * @@ -72,24 +73,24 @@ import sun.misc.Unsafe; * *

This class also includes nested class {@link KeySet} * that provides space-efficient Set views of maps, also supporting - * method intern, which may be of use in canonicalizing + * method {@code intern}, which may be of use in canonicalizing * elements. * *

When used with (Weak or Soft) Reference keys and/or values, - * elements that have asynchronously become null are + * elements that have asynchronously become {@code null} are * treated as absent from the map and (eventually) removed from maps * via a background thread common across all maps. Because of the * potential for asynchronous clearing of References, methods such as - * containsValue have weaker guarantees than you might + * {@code containsValue} have weaker guarantees than you might * expect even in the absence of other explicitly concurrent - * operations. For example containsValue(value) may - * return true even if value is no longer available upon + * operations. For example {@code containsValue(value)} may + * return true even if {@code value} is no longer available upon * return from the method. * *

When Equivalences other than equality are used, the returned - * collections may violate the specifications of Map and/or - * Set interfaces, which mandate the use of the - * equals method when comparing objects. The methods of this + * collections may violate the specifications of {@code Map} and/or + * {@code Set} interfaces, which mandate the use of the + * {@code equals} method when comparing objects. The methods of this * class otherwise have properties similar to those of {@link * java.util.ConcurrentHashMap} under its default settings. To * adaptively maintain semantics and performance under varying @@ -110,8 +111,8 @@ import sun.misc.Unsafe; * @param the type of keys maintained by this map * @param the type of mapped values */ -public class CustomConcurrentHashMap extends AbstractMap - implements ConcurrentMap, Serializable { +public class CustomConcurrentHashMap extends AbstractMap + implements ConcurrentMap, Serializable { private static final long serialVersionUID = 7249069246764182397L; /* @@ -165,8 +166,8 @@ public class CustomConcurrentHashMapK may be - * entered into a Map, any Object may be tested for + * java.util.Map}: While only elements of {@code K} may be + * entered into a Map, any {@code Object} may be tested for * membership. Note that the performance of hash maps is heavily * dependent on the quality of hash functions. */ @@ -224,9 +225,9 @@ public class CustomConcurrentHashMapnull if there is no mapping. + * or {@code null} if there is no mapping. */ - public static interface MappingFunction { + public static interface MappingFunction { /** * Returns a value for the given key, or null if there is no * mapping. If this function throws an (unchecked) exception, @@ -244,10 +245,10 @@ public class CustomConcurrentHashMapnull if there is - * no mapping + * current value to a new value, or {@code null} if there is + * no mapping. */ - public static interface RemappingFunction { + public static interface RemappingFunction { /** * Returns a new value for the given key and its current, or * null if there is no mapping. @@ -320,7 +321,7 @@ public class CustomConcurrentHashMap= MAX_SEGMENT_CAPACITY) return oldTable; - Node[] newTable = - (Node[])new Node[oldCapacity<<1]; + Node[] newTable = new Node[oldCapacity<<1]; int sizeMask = newTable.length - 1; NodeFactory fac = cchm.factory; for (int i = 0; i < oldCapacity ; i++) { @@ -540,11 +539,11 @@ public class CustomConcurrentHashMaptrue if this map contains a key equivalent to + * Returns {@code true} if this map contains a key equivalent to * the given key with respect to this map's key Equivalence. * - * @param key possible key - * @return true if this map contains the specified key + * @param key possible key + * @return {@code true} if this map contains the specified key * @throws NullPointerException if the specified key is null */ public boolean containsKey(Object key) { @@ -697,11 +696,11 @@ public class CustomConcurrentHashMapnull if - * there is no mapping. + * @param key possible key + * @return the value associated with the key, or {@code null} if + * there is no mapping * @throws NullPointerException if the specified key is null */ public V get(Object key) { @@ -752,8 +751,8 @@ public class CustomConcurrentHashMapkey, or - * null if there was no mapping for key + * @return the previous value associated with {@code key}, or + * {@code null} if there was no mapping for {@code key} * @throws NullPointerException if the specified key or value is null */ public V put(K key, V value) { @@ -764,7 +763,7 @@ public class CustomConcurrentHashMapnull if there was no mapping for the key + * or {@code null} if there was no mapping for the key * @throws NullPointerException if the specified key or value is null */ public V putIfAbsent(K key, V value) { @@ -813,7 +812,7 @@ public class CustomConcurrentHashMapnull if there was no mapping for the key + * or {@code null} if there was no mapping for the key * @throws NullPointerException if the specified key or value is null */ public boolean replace(K key, V oldValue, V newValue) { @@ -845,8 +844,8 @@ public class CustomConcurrentHashMapkey, or - * null if there was no mapping for key + * @return the previous value associated with {@code key}, or + * {@code null} if there was no mapping for {@code key} * @throws NullPointerException if the specified key is null */ public V remove(Object key) { @@ -942,7 +941,7 @@ public class CustomConcurrentHashMaptrue if this map contains no key-value mappings. + * Returns {@code true} if this map contains no key-value mappings. * - * @return true if this map contains no key-value mappings + * @return {@code true} if this map contains no key-value mappings */ public final boolean isEmpty() { final Segment[] segs = this.segments; @@ -997,8 +996,8 @@ public class CustomConcurrentHashMapInteger.MAX_VALUE elements, returns - * Integer.MAX_VALUE. + * map contains more than {@code Integer.MAX_VALUE} elements, returns + * {@code Integer.MAX_VALUE}. * * @return the number of key-value mappings in this map */ @@ -1014,14 +1013,14 @@ public class CustomConcurrentHashMaptrue if this map maps one or more keys to a + * Returns {@code true} if this map maps one or more keys to a * value equivalent to the given value with respect to this map's * value Equivalence. Note: This method requires a full internal * traversal of the hash table, and so is much slower than method - * containsKey. + * {@code containsKey}. * * @param value value whose presence in this map is to be tested - * @return true if this map maps one or more keys to the + * @return {@code true} if this map maps one or more keys to the * specified value * @throws NullPointerException if the specified value is null */ @@ -1091,12 +1090,12 @@ public class CustomConcurrentHashMapnull if the computation - * returned null. + * the specified key, or {@code null} if the computation + * returned {@code null} * @throws NullPointerException if the specified key or mappingFunction - * is null, + * is null * @throws RuntimeException or Error if the mappingFunction does so, - * in which case the mapping is left unestablished. + * in which case the mapping is left unestablished */ public V computeIfAbsent(K key, MappingFunction mappingFunction) { if (key == null || mappingFunction == null) @@ -1165,9 +1164,9 @@ public class CustomConcurrentHashMapnull if the computation returned null + * {@code null} if the computation returned {@code null} * @throws NullPointerException if the specified key or remappingFunction - * is null, + * is null * @throws RuntimeException or Error if the remappingFunction does so, * in which case the mapping is left in its previous state */ @@ -1433,12 +1432,12 @@ public class CustomConcurrentHashMapIterator.remove, Set.remove, - * removeAll, retainAll, and clear - * operations. It does not support the add or - * addAll operations. + * via the {@code Iterator.remove}, {@code Set.remove}, + * {@code removeAll}, {@code retainAll}, and {@code clear} + * operations. It does not support the {@code add} or + * {@code addAll} operations. * - *

The view's iterator is a "weakly consistent" iterator + *

The view's {@code iterator} is a "weakly consistent" iterator * that will never throw {@link ConcurrentModificationException}, * and guarantees to traverse elements as they existed upon * construction of the iterator, and may (but is not guaranteed to) @@ -1454,12 +1453,12 @@ public class CustomConcurrentHashMapIterator.remove, - * Collection.remove, removeAll, - * retainAll, and clear operations. It does not - * support the add or addAll operations. + * mapping from this map, via the {@code Iterator.remove}, + * {@code Collection.remove}, {@code removeAll}, + * {@code retainAll}, and {@code clear} operations. It does not + * support the {@code add} or {@code addAll} operations. * - *

The view's iterator is a "weakly consistent" iterator + *

The view's {@code iterator} is a "weakly consistent" iterator * that will never throw {@link ConcurrentModificationException}, * and guarantees to traverse elements as they existed upon * construction of the iterator, and may (but is not guaranteed to) @@ -1475,12 +1474,12 @@ public class CustomConcurrentHashMapIterator.remove, Set.remove, - * removeAll, retainAll, and clear - * operations. It does not support the add or - * addAll operations. + * via the {@code Iterator.remove}, {@code Set.remove}, + * {@code removeAll}, {@code retainAll}, and {@code clear} + * operations. It does not support the {@code add} or + * {@code addAll} operations. * - *

The view's iterator is a "weakly consistent" iterator + *

The view's {@code iterator} is a "weakly consistent" iterator * that will never throw {@link ConcurrentModificationException}, * and guarantees to traverse elements as they existed upon * construction of the iterator, and may (but is not guaranteed to) @@ -1495,13 +1494,13 @@ public class CustomConcurrentHashMaptrue if the given object is also a map of the + * Returns {@code true} if the given object is also a map of the * same size, holding keys that are equal using this Map's key * Equivalence, and which map to values that are equal according * to this Map's value equivalence. * * @param o object to be compared for equality with this map - * @return true if the specified object is equal to this map + * @return {@code true} if the specified object is equal to this map */ public boolean equals(Object o) { if (o == this) @@ -1538,7 +1537,7 @@ public class CustomConcurrentHashMapentrySet() view, which in turn are the hash codes + * {@code entrySet()} view, which in turn are the hash codes * computed using key and value Equivalences for this Map. * @return the hash code */ @@ -1551,8 +1550,8 @@ public class CustomConcurrentHashMapCollections.newSetFromMap applied to a - * CustomConcurrentHashMap, but possibly more + * {@code Collections.newSetFromMap} applied to a + * {@code CustomConcurrentHashMap}, but possibly more * space-efficient. The set does not permit null elements. The * set is serializable; however, serializing a set that uses soft * or weak references can give unpredictable results. @@ -1600,7 +1599,7 @@ public class CustomConcurrentHashMap cchm; /** - * Creates a set with the given parameters + * Creates a set with the given parameters. * @param strength the strength of elements * @param equivalence the Equivalence to use * @param expectedSize an estimate of the number of elements @@ -1621,7 +1620,7 @@ public class CustomConcurrentHashMaptrue if this set contains an + * Returns {@code true} if this set contains an * element equivalent to the given element with respect * to this set's Equivalence. * @param o element whose presence in this set is to be tested - * @return true if this set contains the specified element + * @return {@code true} if this set contains the specified element */ public boolean contains(Object o) { return cchm.containsKey(o); @@ -1656,7 +1655,7 @@ public class CustomConcurrentHashMaptrue if this set did not already contain + * @return {@code true} if this set did not already contain * the specified element */ public boolean add(K e) { @@ -1668,16 +1667,16 @@ public class CustomConcurrentHashMaptrue if the set contained the specified element + * @return {@code true} if the set contained the specified element */ public boolean remove(Object o) { return cchm.remove(o) != null; } /** - * Returns true if this set contains no elements. + * Returns {@code true} if this set contains no elements. * - * @return true if this set contains no elements + * @return {@code true} if this set contains no elements */ public boolean isEmpty() { return cchm.isEmpty(); @@ -1722,7 +1721,7 @@ public class CustomConcurrentHashMap getReclamationQueue() { ReferenceQueue q = refQueue; @@ -1793,7 +1792,7 @@ public class CustomConcurrentHashMap() { - public Unsafe run() throws Exception { - return getUnsafePrivileged(); - }}); - } catch (java.security.PrivilegedActionException e) { - throw e.getCause(); - } - } - } - - private static Unsafe getUnsafePrivileged() - throws NoSuchFieldException, IllegalAccessException { - Field f = Unsafe.class.getDeclaredField("theUnsafe"); - f.setAccessible(true); - return (Unsafe) f.get(null); - } - static { try { UNSAFE = getUnsafe(); tableBase = UNSAFE.arrayBaseOffset(Node[].class); - int s = UNSAFE.arrayIndexScale(Node[].class); - if ((s & (s-1)) != 0) + int scale = UNSAFE.arrayIndexScale(Node[].class); + if ((scale & (scale - 1)) != 0) throw new Error("data type scale not a power of two"); - tableShift = 31 - Integer.numberOfLeadingZeros(s); + tableShift = 31 - Integer.numberOfLeadingZeros(scale); segmentsBase = UNSAFE.arrayBaseOffset(Segment[].class); - s = UNSAFE.arrayIndexScale(Segment[].class); - if ((s & (s-1)) != 0) + scale = UNSAFE.arrayIndexScale(Segment[].class); + if ((scale & (scale - 1)) != 0) throw new Error("data type scale not a power of two"); - segmentsShift = 31 - Integer.numberOfLeadingZeros(s); + segmentsShift = 31 - Integer.numberOfLeadingZeros(scale); } catch (Throwable e) { throw new RuntimeException("Could not initialize intrinsics", e); } } // Fenced store into segment table array. Unneeded when we have Fences - static final void storeNode(Node[] table, - int i, Node r) { + static final void storeNode(Node[] table, + int i, Node r) { long nodeOffset = ((long) i << tableShift) + tableBase; UNSAFE.putOrderedObject(table, nodeOffset, r); } - static final void storeSegment(Segment[] segs, - int i, Segment s) { + static final void storeSegment(Segment[] segs, + int i, Segment s) { long segmentOffset = ((long) i << segmentsShift) + segmentsBase; UNSAFE.putOrderedObject(segs, segmentOffset, s); } - + /** + * Returns a sun.misc.Unsafe. Suitable for use in a 3rd party package. + * Replace with a simple call to Unsafe.getUnsafe when integrating + * into a jdk. + * + * @return a sun.misc.Unsafe + */ + private static sun.misc.Unsafe getUnsafe() { + try { + return sun.misc.Unsafe.getUnsafe(); + } catch (SecurityException tryReflectionInstead) {} + try { + return java.security.AccessController.doPrivileged + (new java.security.PrivilegedExceptionAction() { + public sun.misc.Unsafe run() throws Exception { + Class k = sun.misc.Unsafe.class; + for (java.lang.reflect.Field f : k.getDeclaredFields()) { + f.setAccessible(true); + Object x = f.get(null); + if (k.isInstance(x)) + return k.cast(x); + } + throw new NoSuchFieldError("the Unsafe"); + }}); + } catch (java.security.PrivilegedActionException e) { + throw new RuntimeException("Could not initialize intrinsics", + e.getCause()); + } + } }