CustomConcurrentHashMap.java

/*
 * 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/publicdomain/zero/1.0/
 */

package extra166y;
import java.lang.ref.*;
import java.lang.reflect.*;
import java.io.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.*;
import sun.misc.Unsafe;

/**
 * A {@link java.util.ConcurrentMap} supporting user-defined
 * equivalence comparisons, soft, weak, or strong keys and values, and
 * user-supplied computational methods for setting and updating
 * values. In particular: <ul>
 *
 *   <li> Identity-based, Equality-based or User-definable {@link
 *        Equivalence}-based comparisons controlling membership.
 *
 *   <li> {@linkplain SoftReference Soft}, {@linkplain
 *        WeakReference weak} or strong (regular) keys and values.
 *
 *   <li> User-definable {@code MappingFunctions} that may be
 *        used in method {@link
 *        CustomConcurrentHashMap#computeIfAbsent} to atomically
 *        establish a computed value, along with
 *        {@code RemappingFunctions} that can be used in method
 *        {@link CustomConcurrentHashMap#compute} to atomically
 *        replace values.
 *
 *    <li>Factory methods returning specialized forms for {@code int}
 *        keys and/or values, that may be more space-efficient
 *
 * </ul>
 *
 * Per-map settings are established in constructors, as in the
 * following usages (that assume static imports to simplify expression
 * of configuration parameters):
 *
 * <pre>
 * {@code
 * identityMap = new CustomConcurrentHashMap<Person,Salary>
 *     (STRONG, IDENTITY, STRONG, EQUALS, 0);
 * weakKeyMap = new CustomConcurrentHashMap<Person,Salary>
 *     (WEAK, IDENTITY, STRONG, EQUALS, 0);
 *     .weakKeys());
 * byNameMap = new CustomConcurrentHashMap<Person,Salary>
 *     (STRONG,
 *      new Equivalence<Person>() {
 *          public boolean equal(Person k, Object x) {
 *            return x instanceof Person && k.name.equals(((Person)x).name);
 *          }
 *          public int hash(Object x) {
 *             return (x instanceof Person) ? ((Person)x).name.hashCode() : 0;
 *          }
 *        },
 *      STRONG, EQUALS, 0);
 * }
 * </pre>
 *
 * The first usage above provides a replacement for {@link
 * java.util.IdentityHashMap}, and the second a replacement for {@link
 * java.util.WeakHashMap}, adding concurrency, asynchronous cleanup,
 * and identity-based equality for keys. The third usage
 * illustrates a map with a custom Equivalence that looks only at the
 * name field of a (fictional) Person class.
 *
 * <p>This class also includes nested class {@link KeySet}
 * that provides space-efficient Set views of maps, also supporting
 * method {@code intern}, which may be of use in canonicalizing
 * elements.
 *
 * <p>When used with (Weak or Soft) Reference keys and/or values,
 * 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
 * {@code containsValue} have weaker guarantees than you might
 * expect even in the absence of other explicitly concurrent
 * operations. For example {@code containsValue(value)} may
 * return true even if {@code value} is no longer available upon
 * return from the method.
 *
 * <p>When Equivalences other than equality are used, the returned
 * 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
 * conditions, this class does <em>not</em> support load factor or
 * concurrency level parameters.  This class does not permit null keys
 * or values. This class is serializable; however, serializing a map
 * that uses soft or weak references can give unpredictable results.
 * This class supports all optional operations of the {@code
 * ConcurrentMap} interface.  It supports have <i>weakly consistent
 * iteration</i>: an iterator over one of the map's view collections
 * may reflect some, all or none of the changes made to the collection
 * after the iterator was created.
 *
 * <p>This class is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @param <K> the type of keys maintained by this map
 * @param <V> the type of mapped values
 */
public class CustomConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable {
    private static final long serialVersionUID = 7249069246764182397L;

    /*
     * This class uses a similar approach as ConcurrentHashMap, but
     * makes different internal tradeoffs, mainly (1) We use more
     * segments, but lazily initialize them; and (2) Links connecting
     * nodes are not immutable, enabling unsplicing.  These two
     * adjustments help improve concurrency in the face of heavier
     * per-element mechanics and the increased load due to reference
     * removal, while still keeping footprint etc reasonable.
     *
     * Additionally, because Reference keys/values may become null
     * asynchronously, we cannot ensure snapshot integrity in methods
     * such as containsValue, so do not try to obtain them (so, no
     * modCounts etc).
     *
     * Also, the volatility of Segment count vs table fields are
     * swapped, enabled by ensuring fences on new node assignments.
     */


    /**
     * The strength of keys and values that may be held by
     * maps. strong denotes ordinary objects. weak and soft denote the
     * corresponding {@link java.lang.ref.Reference} types.
     */
    public enum Strength {
        strong("Strong"), weak("Weak"), soft("Soft");
        private final String name;
        Strength(String name) { this.name = name; }
        String getName() { return name; }
    };


    /** The strength of ordinary references */
    public static final Strength STRONG = Strength.strong;

    /** The strength of weak references */
    public static final Strength WEAK   = Strength.weak;

    /** The strength of soft references */
    public static final Strength SOFT   = Strength.soft;

    /** Config string for self-map (Set view) refs */
    private static final String SELF_STRING = "Self";

    /** Config string for int maps */
    private static final String INT_STRING = "Int";

    /**
     * An object performing equality comparisons, along with a hash
     * function consistent with this comparison.  The type signatures
     * of the methods of this interface reflect those of {@link
     * 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.
     */
    public static interface Equivalence<K> {
        /**
         * Returns true if the given objects are considered equal.
         * This function must obey an equivalence relation:
         * equal(a, a) is always true, equal(a, b) implies equal(b, a),
         * and (equal(a, b) &amp;&amp; equal(b, c) implies equal(a, c).
         * Note that the second argument need not be known to have
         * the same declared type as the first.
         * @param key a key in, or being placed in, the map
         * @param x an object queried for membership
         * @return true if considered equal
         */
        boolean equal(K key, Object x);
        /**
         * Returns a hash value such that equal(a, b) implies
         * hash(a)==hash(b).
         * @param x an object queried for membership
         * @return a hash value
         */
        int hash(Object x);
    }

    // builtin equivalences

    static final class EquivalenceUsingIdentity
        implements Equivalence<Object>, Serializable {
        private static final long serialVersionUID = 7259069246764182397L;
        public final boolean equal(Object a, Object b) { return a == b; }
        public final int hash(Object a) { return System.identityHashCode(a); }
    }

    static final class EquivalenceUsingEquals
        implements Equivalence<Object>, Serializable {
        private static final long serialVersionUID = 7259069247764182397L;
        public final boolean equal(Object a, Object b) { return a.equals(b); }
        public final int hash(Object a) { return a.hashCode(); }
    }

    /**
     * An Equivalence object performing identity-based comparisons
     * and using {@link System#identityHashCode} for hashing
     */
    public static final Equivalence<Object> IDENTITY =
        new EquivalenceUsingIdentity();

    /**
     * An Equivalence object performing {@link Object#equals} based comparisons
     * and using {@link Object#hashCode} hashing
     */
    public static final Equivalence<Object> EQUALS =
        new EquivalenceUsingEquals();

    /**
     * A function computing a mapping from the given key to a value,
     * or {@code null} if there is no mapping.
     */
    public static interface MappingFunction<K,V> {
        /**
         * Returns a value for the given key, or null if there is no
         * mapping. If this function throws an (unchecked) exception,
         * the exception is rethrown to its caller, and no mapping is
         * recorded.  Because this function is invoked within
         * atomicity control, the computation should be short and
         * simple. The most common usage is to construct a new object
         * serving as an initial mapped value.
         *
         * @param key the (non-null) key
         * @return a value, or null if none
         */
        V map(K key);
    }

    /**
     * A function computing a new mapping from the given key and its
     * current value to a new value, or {@code null} if there is
     * no mapping.
     */
    public static interface RemappingFunction<K,V> {
        /**
         * Returns a new value for the given key and its current, or
         * null if there is no mapping.
         * @param key the key
         * @param value the current value, or null if none
         * @return a value, or null if none
         */
        V remap(K key, V value);
    }

    /**
     * An object that may be subject to cleanup operations when
     * removed from a {@link java.lang.ref.ReferenceQueue}
     */
    static interface Reclaimable {
        /**
         * The action taken upon removal of this object
         * from a ReferenceQueue.
         */
        void onReclamation();
    }

    /**
     * A factory for Nodes.
     */
    static interface NodeFactory extends Serializable {
        /**
         * Creates and returns a Node using the given parameters.
         *
         * @param locator an opaque immutable locator for this node
         * @param key the (non-null) immutable key
         * @param value the (non-null) volatile value
         * @param cchm the table creating this node
         * @param linkage an opaque volatile linkage for maintaining this node
         */
        Node newNode(int locator, Object key, Object value,
                     CustomConcurrentHashMap cchm, Node linkage);
    }

    /**
     * An object maintaining a key-value mapping. Nodes provide
     * methods that are intended to used <em>only</em> by the map
     * creating the node. This includes methods used solely for
     * internal bookkeeping by maps, that must be treating opaquely by
     * implementation classes. (This requirement stems from the fact
     * that concrete implementations may be required to subclass
     * {@link java.lang.ref.Reference} or other classes, so a base
     * class cannot be established.)
     *
     * This interface uses raw types as the lesser of evils.
     * Otherwise we'd encounter almost as many unchecked casts when
     * nodes are used across sets, etc.
     */
    static interface Node extends Reclaimable {
        /**
         * Returns the key established during the creation of this node.
         * Note: This method is named "get" rather than "getKey"
         * to simplify usage of Reference keys.
         * @return the key
         */
        Object get();

        /**
         * Returns the locator established during the creation of this node.
         * @return the locator
         */
        int getLocator();

        /**
         * Returns the value established during the creation of this
         * node or, if since updated, the value set by the most
         * recent call to setValue, or throws an exception if
         * value could not be computed.
         * @return the value
         * @throws RuntimeException or Error if computeValue failed
         */
        Object getValue();

        /**
         * Nodes the value to be returned by the next call to getValue.
         * @param value the value
         */
        void setValue(Object value);

        /**
         * Returns the linkage established during the creation of this
         * node or, if since updated, the linkage set by the most
         * recent call to setLinkage.
         * @return the linkage
         */
        Node getLinkage();

        /**
         * Records the linkage to be returned by the next call to getLinkage.
         * @param linkage the linkage
         */
        void setLinkage(Node linkage);
    }

    /**
     * Each Segment holds a count and table corresponding to a segment
     * of the table. This class contains only those methods for
     * directly assigning these fields, which must only be called
     * while holding locks.
     */
    static final class Segment extends ReentrantLock {
        volatile Node[] table;
        int count;

        final void decrementCount() {
            if (--count == 0)
                table = null;
        }

        final void clearCount() {
            count = 0;
            table = null;
        }

        final void incrementCount() {
            ++count;
        }

        final Node[] getTableForTraversal() {
            return table;
        }

        final Node[] getTableForAdd(CustomConcurrentHashMap cchm) {
            int len;
            Node[] tab = table;
            if (tab == null ||  // 3/4 threshold
                ((len = tab.length) - (len >>> 2)) < count)
                return resizeTable(cchm);
            else
                return tab;
        }

        /**
         * See the similar code in ConcurrentHashMap for explanation.
         */
        final Node[] resizeTable(CustomConcurrentHashMap cchm) {
            Node[] oldTable = table;
            if (oldTable == null)
                return table = new Node[cchm.initialSegmentCapacity];

            int oldCapacity = oldTable.length;
            if (oldCapacity >= MAX_SEGMENT_CAPACITY)
                return oldTable;
            Node[] newTable = new Node[oldCapacity<<1];
            int sizeMask = newTable.length - 1;
            NodeFactory fac = cchm.factory;
            for (int i = 0; i < oldCapacity ; i++) {
                Node e = oldTable[i];

                if (e != null) {
                    Node next = e.getLinkage();
                    int idx = e.getLocator() & sizeMask;

                    //  Single node on list
                    if (next == null)
                        newTable[idx] = e;

                    else {
                        // Reuse trailing consecutive sequence at same slot
                        Node lastRun = e;
                        int lastIdx = idx;
                        for (Node last = next;
                             last != null;
                             last = last.getLinkage()) {
                            int k = last.getLocator() & sizeMask;
                            if (k != lastIdx) {
                                lastIdx = k;
                                lastRun = last;
                            }
                        }
                        newTable[lastIdx] = lastRun;

                        // Clone all remaining nodes
                        for (Node p = e; p != lastRun; p = p.getLinkage()) {
                            int ph = p.getLocator();
                            int k = ph & sizeMask;
                            Object pk = p.get();
                            Object pv;
                            if (pk == null ||
                                (pv = p.getValue()) == null)
                                --count;
                            else
                                newTable[k] =
                                    fac.newNode(ph, pk, pv, cchm, newTable[k]);
                        }
                    }
                }
            }
            return table = newTable;
        }
    }

    // Hardwire 64 segments

    static final int SEGMENT_BITS         = 6;
    static final int NSEGMENTS            = 1 << SEGMENT_BITS;
    static final int SEGMENT_MASK         = NSEGMENTS - 1;
    static final int SEGMENT_SHIFT        = 32 - SEGMENT_BITS;
    static final int MIN_SEGMENT_CAPACITY = 4;
    static final int MAX_SEGMENT_CAPACITY = 1 << (32 - SEGMENT_BITS);

    /**
     * Applies a supplemental hash function to a given hashCode, which
     * defends against poor quality hash functions.  This is critical
     * because we use power-of-two length hash tables, that otherwise
     * encounter collisions for hashCodes that do not differ in lower
     * or upper bits.
     */
    static int spreadHash(int h) {
        // Spread bits to regularize both segment and index locations,
        // using variant of single-word Wang/Jenkins hash.
        h += (h <<  15) ^ 0xffffcd7d;
        h ^= (h >>> 10);
        h += (h <<   3);
        h ^= (h >>>  6);
        h += (h <<   2) + (h << 14);
        return h ^ (h >>> 16);
    }

    /**
     * The segments, each of which acts as a hash table
     */
    transient volatile Segment[] segments;

    /**
     * The factory for this map
     */
    final NodeFactory factory;

    /**
     * Equivalence object for keys
     */
    final Equivalence<? super K> keyEquivalence;

    /**
     * Equivalence object for values
     */
    final Equivalence<? super V> valueEquivalence;

    /**
     * The initial size of Segment tables when they are first constructed
     */
    final int initialSegmentCapacity;

    // Cached view objects
    transient Set<K> keySet;
    transient Set<Map.Entry<K,V>> entrySet;
    transient Collection<V> values;

    /**
     * Internal constructor to set factory, equivalences and segment
     * capacities, and to create segments array.
     */
    CustomConcurrentHashMap(String ks, Equivalence<? super K> keq,
                            String vs, Equivalence<? super V> veq,
                            int expectedSize) {
        if (keq == null || veq == null)
            throw new NullPointerException();
        this.keyEquivalence = keq;
        this.valueEquivalence = veq;
        // Reflectively assemble factory name
        String factoryName =
            CustomConcurrentHashMap.class.getName() + "$" +
            ks + "Key" +
            vs + "ValueNodeFactory";
        try {
            this.factory = (NodeFactory)
                (Class.forName(factoryName).newInstance());
        } catch (Exception ex) {
            throw new Error("Cannot instantiate " + factoryName);
        }
        int es = expectedSize;
        if (es == 0)
            this.initialSegmentCapacity = MIN_SEGMENT_CAPACITY;
        else {
            int sc = (int)((1L + (4L * es) / 3) >>> SEGMENT_BITS);
            if (sc < MIN_SEGMENT_CAPACITY)
                sc = MIN_SEGMENT_CAPACITY;
            int capacity = MIN_SEGMENT_CAPACITY; // ensure power of two
            while (capacity < sc)
                capacity <<= 1;
            if (capacity > MAX_SEGMENT_CAPACITY)
                capacity = MAX_SEGMENT_CAPACITY;
            this.initialSegmentCapacity = capacity;
        }
        this.segments = new Segment[NSEGMENTS];
    }

    /**
     * Creates a new CustomConcurrentHashMap with the given parameters.
     * @param keyStrength the strength for keys
     * @param keyEquivalence the Equivalence to use for keys
     * @param valueStrength the strength for values
     * @param valueEquivalence the Equivalence to use for values
     * @param expectedSize an estimate of the number of elements
     * that will be held in the map. If no estimate is known,
     * zero is an acceptable value.
     */
    public CustomConcurrentHashMap(Strength keyStrength,
                                   Equivalence<? super K> keyEquivalence,
                                   Strength valueStrength,
                                   Equivalence<? super V> valueEquivalence,
                                   int expectedSize) {
        this(keyStrength.getName(), keyEquivalence,
             valueStrength.getName(), valueEquivalence,
             expectedSize);
    }

    /**
     * Creates a new CustomConcurrentHashMap with strong keys and
     * values, and equality-based equivalence.
     */
    public CustomConcurrentHashMap() {
        this(STRONG, EQUALS, STRONG, EQUALS, 0);
    }

    /**
     * Returns a new map using Integer keys and the given value
     * parameters.
     * @param valueStrength the strength for values
     * @param valueEquivalence the Equivalence to use for values
     * @param expectedSize an estimate of the number of elements
     * that will be held in the map. If no estimate is known,
     * zero is an acceptable value.
     * @return the map
     */
    public static <ValueType> CustomConcurrentHashMap<Integer, ValueType>
        newIntKeyMap(Strength valueStrength,
                     Equivalence<? super ValueType> valueEquivalence,
                     int expectedSize) {
        return new CustomConcurrentHashMap<Integer, ValueType>
            (INT_STRING, EQUALS, valueStrength.getName(), valueEquivalence,
             expectedSize);
    }

    /**
     * Returns a new map using the given key parameters and Integer values.
     * @param keyStrength the strength for keys
     * @param keyEquivalence the Equivalence to use for keys
     * @param expectedSize an estimate of the number of elements
     * that will be held in the map. If no estimate is known,
     * zero is an acceptable value.
     * @return the map
     */
    public static <KeyType> CustomConcurrentHashMap<KeyType, Integer>
        newIntValueMap(Strength keyStrength,
                       Equivalence<? super KeyType> keyEquivalence,
                       int expectedSize) {
        return new CustomConcurrentHashMap<KeyType, Integer>
            (keyStrength.getName(), keyEquivalence, INT_STRING, EQUALS,
             expectedSize);
    }

    /**
     * Returns a new map using Integer keys and values.
     * @param expectedSize an estimate of the number of elements
     * that will be held in the map. If no estimate is known,
     * zero is an acceptable value.
     * @return the map
     */
    public static CustomConcurrentHashMap<Integer, Integer>
        newIntKeyIntValueMap(int expectedSize) {
        return new CustomConcurrentHashMap<Integer, Integer>
            (INT_STRING, EQUALS, INT_STRING, EQUALS,
             expectedSize);
    }

    /**
     * Returns the segment for traversing table for key with given hash.
     * @param hash the hash code for the key
     * @return the segment, or null if not yet initialized
     */
    final Segment getSegmentForTraversal(int hash) {
        return segments[(hash >>> SEGMENT_SHIFT) & SEGMENT_MASK];
    }

    /**
     * Returns the segment for possibly inserting into the table
     * associated with given hash, constructing it if necessary.
     * @param hash the hash code for the key
     * @return the segment
     */
    final Segment getSegmentForAdd(int hash) {
        Segment[] segs = segments;
        int index = (hash >>> SEGMENT_SHIFT) & SEGMENT_MASK;
        Segment seg = segs[index];
        if (seg == null) {
            synchronized (segs) {
                seg = segs[index];
                if (seg == null) {
                    seg = new Segment();
                    // Fences.preStoreFence(seg);
                    // segs[index] = seg;
                    storeSegment(segs, index, seg);
                }
            }
        }
        return seg;
    }

    /**
     * Returns node for key, or null if none.
     */
    final Node findNode(Object key, int hash, Segment seg) {
        if (seg != null) {
            Node[] tab = seg.getTableForTraversal();
            if (tab != null) {
                Node p = tab[hash & (tab.length - 1)];
                while (p != null) {
                    Object k = p.get();
                    if (k == key ||
                        (k != null &&
                         p.getLocator() == hash &&
                         keyEquivalence.equal((K)k, key)))
                        return p;
                    p = p.getLinkage();
                }
            }
        }
        return null;
    }

    /**
     * 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 {@code true} if this map contains the specified key
     * @throws NullPointerException if the specified key is null
     */
    public boolean containsKey(Object key) {
        if (key == null)
            throw new NullPointerException();
        int hash = spreadHash(keyEquivalence.hash(key));
        Segment seg = getSegmentForTraversal(hash);
        Node r = findNode(key, hash, seg);
        return r != null && r.getValue() != null;
    }

    /**
     * Returns the value associated with a key equivalent to the given
     * key with respect to this map's key Equivalence, or {@code null}
     * if no such mapping exists.
     *
     * @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) {
        if (key == null)
            throw new NullPointerException();
        int hash = spreadHash(keyEquivalence.hash(key));
        Segment seg = getSegmentForTraversal(hash);
        Node r = findNode(key, hash, seg);
        if (r == null)
            return null;
        return (V)(r.getValue());
    }

    /**
     * Shared implementation for put, putIfAbsent
     */
    final V doPut(K key, V value, boolean onlyIfNull) {
        if (key == null || value == null)
            throw new NullPointerException();
        V oldValue = null;
        int hash = spreadHash(keyEquivalence.hash(key));
        Segment seg = getSegmentForAdd(hash);
        seg.lock();
        try {
            Node r = findNode(key, hash, seg);
            if (r != null) {
                oldValue = (V)(r.getValue());
                if (!onlyIfNull || oldValue == null)
                    r.setValue(value);
            }
            else {
                Node[] tab = seg.getTableForAdd(this);
                int i = hash & (tab.length - 1);
                r = factory.newNode(hash, key, value, this, tab[i]);
                // Fences.preStoreFence(r);
                // tab[i] = r;
                storeNode(tab, i, r);
                seg.incrementCount();
            }
        } finally {
            seg.unlock();
        }
        return oldValue;
    }

    /**
     * Maps the specified key to the specified value in this map.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified 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) {
        return doPut(key, value, false);
    }

    /**
     * {@inheritDoc}
     *
     * @return the previous value associated with the specified 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) {
        return doPut(key, value, true);
    }

    /**
     * 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 m mappings to be stored in this map
     */
    public void putAll(Map<? extends K, ? extends V> m) {
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
            put(e.getKey(), e.getValue());
    }

    /**
     * {@inheritDoc}
     *
     * @throws NullPointerException if any of the arguments are null
     */
    public V replace(K key, V value) {
        if (key == null || value == null)
            throw new NullPointerException();
        V oldValue = null;
        int hash = spreadHash(keyEquivalence.hash(key));
        Segment seg = getSegmentForTraversal(hash);
        if (seg != null) {
            seg.lock();
            try {
                Node r = findNode(key, hash, seg);
                if (r != null) {
                    oldValue = (V)(r.getValue());
                    r.setValue(value);
                }
            } finally {
                seg.unlock();
            }
        }
        return oldValue;
    }

    /**
     * {@inheritDoc}
     *
     * @return the previous value associated with the specified 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) {
        if (key == null || oldValue == null || newValue == null)
            throw new NullPointerException();
        boolean replaced = false;
        int hash = spreadHash(keyEquivalence.hash(key));
        Segment seg = getSegmentForTraversal(hash);
        if (seg != null) {
            seg.lock();
            try {
                Node r = findNode(key, hash, seg);
                if (r != null) {
                    V v = (V)(r.getValue());
                    if (v == oldValue ||
                        (v != null && valueEquivalence.equal(v, oldValue))) {
                        r.setValue(newValue);
                        replaced = true;
                    }
                }
            } finally {
                seg.unlock();
            }
        }
        return replaced;
    }

    /**
     * Removes the mapping for the specified key.
     *
     * @param  key the key to remove
     * @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) {
        if (key == null)
            throw new NullPointerException();
        V oldValue = null;
        int hash = spreadHash(keyEquivalence.hash(key));
        Segment seg = getSegmentForTraversal(hash);
        if (seg != null) {
            seg.lock();
            try {
                Node[] tab = seg.getTableForTraversal();
                if (tab != null) {
                    int i = hash & (tab.length - 1);
                    Node pred = null;
                    Node p = tab[i];
                    while (p != null) {
                        Node n = p.getLinkage();
                        Object k = p.get();
                        if (k == key ||
                            (k != null &&
                             p.getLocator() == hash &&
                             keyEquivalence.equal((K)k, key))) {
                            oldValue = (V)(p.getValue());
                            if (pred == null)
                                tab[i] = n;
                            else
                                pred.setLinkage(n);
                            seg.decrementCount();
                            break;
                        }
                        pred = p;
                        p = n;
                    }
                }
            } finally {
                seg.unlock();
            }
        }
        return oldValue;
    }

    /**
     * {@inheritDoc}
     *
     * @throws NullPointerException if the specified key is null
     */
    public boolean remove(Object key, Object value) {
        if (key == null)
            throw new NullPointerException();
        if (value == null)
            return false;
        boolean removed = false;
        int hash = spreadHash(keyEquivalence.hash(key));
        Segment seg = getSegmentForTraversal(hash);
        if (seg != null) {
            seg.lock();
            try {
                Node[] tab = seg.getTableForTraversal();
                if (tab != null) {
                    int i = hash & (tab.length - 1);
                    Node pred = null;
                    Node p = tab[i];
                    while (p != null) {
                        Node n = p.getLinkage();
                        Object k = p.get();
                        if (k == key ||
                            (k != null &&
                             p.getLocator() == hash &&
                             keyEquivalence.equal((K)k, key))) {
                            V v = (V)(p.getValue());
                            if (v == value ||
                                (v != null &&
                                 valueEquivalence.equal(v, value))) {
                                if (pred == null)
                                    tab[i] = n;
                                else
                                    pred.setLinkage(n);
                                seg.decrementCount();
                                removed = true;
                            }
                            break;
                        }
                        pred = p;
                        p = n;
                    }
                }
            } finally {
                seg.unlock();
            }
        }
        return removed;
    }

    /**
     * Removes node if its key or value are null.
     */
    final void removeIfReclaimed(Node r) {
        int hash = r.getLocator();
        Segment seg = getSegmentForTraversal(hash);
        if (seg != null) {
            seg.lock();
            try {
                Node[] tab = seg.getTableForTraversal();
                if (tab != null) {
                    // remove all reclaimed in list
                    int i = hash & (tab.length - 1);
                    Node pred = null;
                    Node p = tab[i];
                    while (p != null) {
                        Node n = p.getLinkage();
                        if (p.get() != null && p.getValue() != null) {
                            pred = p;
                            p = n;
                        }
                        else {
                            if (pred == null)
                                tab[i] = n;
                            else
                                pred.setLinkage(n);
                            seg.decrementCount();
                            p = n;
                        }
                    }
                }
            } finally {
                seg.unlock();
            }
        }
    }

    /**
     * Returns {@code 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;
        for (int i = 0; i < segs.length; ++i) {
            Segment seg = segs[i];
            if (seg != null &&
                seg.getTableForTraversal() != null &&
                seg.count != 0)
                return false;
        }
        return true;
    }

    /**
     * Returns the number of key-value mappings in this map.  If the
     * map contains more than {@code Integer.MAX_VALUE} elements, returns
     * {@code Integer.MAX_VALUE}.
     *