arthas-master.zip

/* * Copyright 2012 The Netty Project * * The Netty Project licenses this file to you under the Apache License, * version 2.0 (the "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at: * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the * License for the specific language governing permissions and limitations * under the License. */ /* * 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 */ package com.taobao.arthas.common.concurrent; import java.lang.ref.Reference; import java.lang.ref.ReferenceQueue; import java.lang.ref.WeakReference; import java.util.AbstractCollection; import java.util.AbstractMap; import java.util.AbstractSet; import java.util.Arrays; import java.util.Collection; import java.util.ConcurrentModificationException; import java.util.Enumeration; import java.util.Hashtable; import java.util.Iterator; import java.util.Map; import java.util.NoSuchElementException; import java.util.Set; import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.ConcurrentMap; import java.util.concurrent.locks.ReentrantLock; /** * An alternative weak-key {@link ConcurrentMap} which is similar to * {@link ConcurrentHashMap}. * @param <K> the type of keys maintained by this map * @param <V> the type of mapped values */ public final class ConcurrentWeakKeyHashMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V> { /* * The basic strategy is to subdivide the table among Segments, * each of which itself is a concurrently readable hash table. */ /** * The default initial capacity for this table, used when not otherwise * specified in a constructor. */ static final int DEFAULT_INITIAL_CAPACITY = 16; /** * The default load factor for this table, used when not otherwise specified * in a constructor. */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * The default concurrency level for this table, used when not otherwise * specified in a constructor. */ static final int DEFAULT_CONCURRENCY_LEVEL = 16; /** * The maximum capacity, used if a higher value is implicitly specified by * either of the constructors with arguments. MUST be a power of two * &lt;= 1&lt;&lt;30 to ensure that entries are indexable using integers. */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * The maximum number of segments to allow; used to bound constructor * arguments. */ static final int MAX_SEGMENTS = 1 << 16; // slightly conservative /** * Number of unsynchronized retries in size and containsValue methods before * resorting to locking. This is used to avoid unbounded retries if tables * undergo continuous modification which would make it impossible to obtain * an accurate result. */ static final int RETRIES_BEFORE_LOCK = 2; /* ---------------- Fields -------------- */ /** * Mask value for indexing into segments. The upper bits of a key's hash * code are used to choose the segment. */ final int segmentMask; /** * Shift value for indexing within segments. */ final int segmentShift; /** * The segments, each of which is a specialized hash table */ final Segment<K, V>[] segments; Set<K> keySet; Set<Map.Entry<K, V>> entrySet; Collection<V> values; /* ---------------- Small Utilities -------------- */ /** * Applies a supplemental hash function to a given hashCode, which defends * against poor quality hash functions. This is critical because * ConcurrentReferenceHashMap uses power-of-two length hash tables, that * otherwise encounter collisions for hashCodes that do not differ in lower * or upper bits. */ private static int hash(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; } /** * Returns the segment that should be used for key with given hash. * * @param hash the hash code for the key * @return the segment */ Segment<K, V> segmentFor(int hash) { return segments[hash >>> segmentShift & segmentMask]; } private static int hashOf(Object key) { return hash(key.hashCode()); } /* ---------------- Inner Classes -------------- */ /** * A weak-key reference which stores the key hash needed for reclamation. */ static final class WeakKeyReference<K> extends WeakReference<K> { final int hash; WeakKeyReference(K key, int hash, ReferenceQueue<Object> refQueue) { super(key, refQueue); this.hash = hash; } public int keyHash() { return hash; } public Object keyRef() { return this; } } /** * ConcurrentReferenceHashMap list entry. Note that this is never exported * out as a user-visible Map.Entry. * * Because the value field is volatile, not final, it is legal wrt * the Java Memory Model for an unsynchronized reader to see null * instead of initial value when read via a data race. Although a * reordering leading to this is not likely to ever actually * occur, the Segment.readValueUnderLock method is used as a * backup in case a null (pre-initialized) value is ever seen in * an unsynchronized access method. */ static final class HashEntry<K, V> { final Object keyRef; final int hash; volatile Object valueRef; final HashEntry<K, V> next; HashEntry( K key, int hash, HashEntry<K, V> next, V value, ReferenceQueue<Object> refQueue) { this.hash = hash; this.next = next; keyRef = new WeakKeyReference<K>(key, hash, refQueue); valueRef = value; } @SuppressWarnings("unchecked") K key() { return ((Reference<K>) keyRef).get(); } V value() { return dereferenceValue(valueRef); } @SuppressWarnings("unchecked") V dereferenceValue(Object value) { if (value instanceof WeakKeyReference) { return ((Reference<V>) value).get(); } return (V) value; } void setValue(V value) { valueRef = value; } @SuppressWarnings("unchecked") static <K, V> HashEntry<K, V>[] newArray(int i) { return new HashEntry[i]; } } /** * Segments are specialized versions of hash tables. This subclasses from * ReentrantLock opportunistically, just to simplify some locking and avoid * separate construction. */ static final class Segment<K, V> extends ReentrantLock { /* * Segments maintain a table of entry lists that are ALWAYS kept in a * consistent state, so can be read without locking. Next fields of * nodes are immutable (final). All list additions are performed at the * front of each bin. This makes it easy to check changes, and also fast * to traverse. When nodes would otherwise be changed, new nodes are * created to replace them. This works well for hash tables since the * bin lists tend to be short. (The average length is less than two fo