http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1e649dc/modules/core/src/main/java/org/jdk8/backport/ConcurrentLinkedHashMap.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/jdk8/backport/ConcurrentLinkedHashMap.java b/modules/core/src/main/java/org/jdk8/backport/ConcurrentLinkedHashMap.java new file mode 100644 index 0000000..8992e77 --- /dev/null +++ b/modules/core/src/main/java/org/jdk8/backport/ConcurrentLinkedHashMap.java @@ -0,0 +1,2170 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. Oracle designates this + * particular file as subject to the "Classpath" exception as provided + * by Oracle in the LICENSE file that accompanied this code. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ + +/* + * This file is available under and governed by the GNU General Public + * License version 2 only, as published by the Free Software Foundation. + * However, the following notice accompanied the original version of this + * file: + * + * 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/ + */ + +/* + * Copyright © 1993, 2013, Oracle and/or its affiliates. + * All rights reserved. + */ + +package org.jdk8.backport; + +import java.util.*; +import java.util.concurrent.*; +import java.util.concurrent.locks.*; + +import static org.jdk8.backport.ConcurrentLinkedHashMap.QueuePolicy.*; + +/** + * A hash table supporting full concurrency of retrievals and + * adjustable expected concurrency for updates. This class obeys the + * same functional specification as {@link java.util.Hashtable}, and + * includes versions of methods corresponding to each method of + * <tt>Hashtable</tt>. However, even though all operations are + * thread-safe, retrieval operations do <em>not</em> entail locking, + * and there is <em>not</em> any support for locking the entire table + * in a way that prevents all access. This class is fully + * interoperable with <tt>Hashtable</tt> in programs that rely on its + * thread safety but not on its synchronization details. + * + * <p> Retrieval operations (including <tt>get</tt>) generally do not + * block, so may overlap with update operations (including + * <tt>put</tt> and <tt>remove</tt>). Retrievals reflect the results + * of the most recently <em>completed</em> update operations holding + * upon their onset. For aggregate operations such as <tt>putAll</tt> + * and <tt>clear</tt>, concurrent retrievals may reflect insertion or + * removal of only some entries. Similarly, Iterators and + * Enumerations return elements reflecting the state of the hash table + * at some point at or since the creation of the iterator/enumeration. + * They do <em>not</em> throw {@link ConcurrentModificationException}. + * However, iterators are designed to be used by only one thread at a time. + * + * <p> The allowed concurrency among update operations is guided by + * the optional <tt>concurrencyLevel</tt> constructor argument + * (default <tt>16</tt>), which is used as a hint for internal sizing. The + * table is internally partitioned to try to permit the indicated + * number of concurrent updates without contention. Because placement + * in hash tables is essentially random, the actual concurrency will + * vary. Ideally, you should choose a value to accommodate as many + * threads as will ever concurrently modify the table. Using a + * significantly higher value than you need can waste space and time, + * and a significantly lower value can lead to thread contention. But + * overestimates and underestimates within an order of magnitude do + * not usually have much noticeable impact. A value of one is + * appropriate when it is known that only one thread will modify and + * all others will only read. Also, resizing this or any other kind of + * hash table is a relatively slow operation, so, when possible, it is + * a good idea to provide estimates of expected table sizes in + * constructors. + * + * <p/> This implementation differs from + * <tt>HashMap</tt> in that it maintains a doubly-linked list running through + * all of its entries. This linked list defines the iteration ordering, + * which is the order in which keys were inserted into the map + * (<i>insertion-order</i>). + * + * <p> NOTE: Access order is not supported by this map. + * + * Note that insertion order is not affected + * if a key is <i>re-inserted</i> into the map. (A key <tt>k</tt> is + * reinserted into a map <tt>m</tt> if <tt>m.put(k, v)</tt> is invoked when + * <tt>m.containsKey(k)</tt> would return <tt>true</tt> immediately prior to + * the invocation.) + * + * <p>An optional {@code maxCap} may be passed to the map constructor to + * create bounded map that will remove stale mappings automatically when new mappings + * are added to the map. + * + * <p/>When iterating over the key set in insertion order one should note that iterator + * will see all removes done since the iterator was created, but will see <b>no</b> + * inserts to map. + * + * <p>This class and its views and iterators implement all of the + * <em>optional</em> methods of the {@link Map} and {@link Iterator} + * interfaces. + * + * <p> Like {@link Hashtable} but unlike {@link HashMap}, this class + * does <em>not</em> allow <tt>null</tt> to be used as a key or value. + * + * @author Doug Lea + * @param <K> the type of keys maintained by this map + * @param <V> the type of mapped values + */ +@SuppressWarnings("NullableProblems") +public class ConcurrentLinkedHashMap<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. + */ + + /* ---------------- Constants -------------- */ + + /** + * The default initial capacity for this table, + * used when not otherwise specified in a constructor. + */ + public static final int DFLT_INIT_CAP = 16; + + /** + * The default load factor for this table, used when not + * otherwise specified in a constructor. + */ + public static final float DFLT_LOAD_FACTOR = 0.75f; + + /** + * The default concurrency level for this table, used when not + * otherwise specified in a constructor. + */ + public static final int DFLT_CONCUR_LVL = 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 <= 1<<30 to ensure that entries are indexable + * using ints. + */ + public static final int MAX_CAP_LIMIT = 1 << 30; + + /** + * The maximum number of segments to allow; used to bound + * constructor arguments. + */ + public static final int MAX_SEGS = 1 << 16; // slightly conservative + + /** + * Number of unsynchronized retries in {@link #size} and {@link #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. + */ + public 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. + */ + private final int segmentMask; + + /** Shift value for indexing within segments. */ + private final int segmentShift; + + /** The segments, each of which is a specialized hash table. */ + private final Segment<K, V>[] segments; + + /** Key set. */ + private Set<K> keySet; + + /** Key set. */ + private Set<K> descKeySet; + + /** Entry set */ + private Set<Map.Entry<K, V>> entrySet; + + /** Entry set in descending order. */ + private Set<Map.Entry<K, V>> descEntrySet; + + /** Values collection. */ + private Collection<V> vals; + + /** Values collection in descending order. */ + private Collection<V> descVals; + + /** Queue containing order of entries. */ + private final ConcurrentLinkedDeque8<HashEntry<K, V>> entryQ; + + /** Atomic variable containing map size. */ + private final LongAdder size = new LongAdder(); + + /** */ + private final LongAdder modCnt = new LongAdder(); + + /** */ + private final int maxCap; + + /** */ + private final QueuePolicy qPlc; + + /* ---------------- Small Utilities -------------- */ + + /** + * Applies a supplemental hash function to a given hashCode, which + * defends against poor quality hash functions. This is critical + * because ConcurrentHashMap uses power-of-two length hash tables, + * that otherwise encounter collisions for hashCodes that do not + * differ in lower or upper bits. + * + * @param h Input hash. + * @return Hash. + */ + private static int hash(int h) { + // Apply base step of MurmurHash; see http://code.google.com/p/smhasher/ + // Despite two multiplies, this is often faster than others + // with comparable bit-spread properties. + h ^= h >>> 16; + h *= 0x85ebca6b; + h ^= h >>> 13; + h *= 0xc2b2ae35; + + return ((h >>> 16) ^ h); + } + + /** + * Returns the segment that should be used for key with given hash. + * + * @param hash the hash code for the key + * @return the segment + */ + private Segment<K, V> segmentFor(int hash) { + return segments[(hash >>> segmentShift) & segmentMask]; + } + + /* ---------------- Inner Classes -------------- */ + + /** + * ConcurrentHashMap 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. + */ + @SuppressWarnings({"PublicInnerClass"}) + public static final class HashEntry<K, V> { + /** Key. */ + private final K key; + + /** Hash of the key after {@code hash()} method is applied. */ + private final int hash; + + /** Value. */ + private volatile V val; + + /** Reference to a node in queue for fast removal operations. */ + private volatile ConcurrentLinkedDeque8.Node node; + + /** Modification count of the map for duplicates exclusion. */ + private volatile int modCnt; + + /** Link to the next entry in a bucket */ + private final HashEntry<K, V> next; + + /** + * @param key Key. + * @param hash Key hash. + * @param next Link to next. + * @param val Value. + */ + HashEntry(K key, int hash, HashEntry<K, V> next, V val) { + this.key = key; + this.hash = hash; + this.next = next; + this.val = val; + } + + /** + * @param key Key. + * @param hash Key hash. + * @param next Link to next. + * @param val Value. + * @param node Queue node. + * @param modCnt Mod count. + */ + HashEntry(K key, int hash, HashEntry<K, V> next, V val, ConcurrentLinkedDeque8.Node node, int modCnt) { + this.key = key; + this.hash = hash; + this.next = next; + this.val = val; + this.node = node; + this.modCnt = modCnt; + } + + /** + * Returns key of this entry. + * + * @return Key. + */ + public K getKey() { + return key; + } + + /** + * Return value of this entry. + * + * @return Value. + */ + public V getValue() { + return val; + } + + /** + * Creates new array of entries. + * + * @param i Size of array. + * @param <K> Key type. + * @param <V> Value type. + * @return Empty array. + */ + @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. + */ + @SuppressWarnings({"TransientFieldNotInitialized"}) + private final class Segment<K, V> extends ReentrantReadWriteLock { + /* + * 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 for the default load factor threshold.) + * + * Read operations can thus proceed without locking, but rely + * on selected uses of volatiles to ensure that completed + * write operations performed by other threads are + * noticed. For most purposes, the "count" field, tracking the + * number of elements, serves as that volatile variable + * ensuring visibility. This is convenient because this field + * needs to be read in many read operations anyway: + * + * - All (unsynchronized) read operations must first read the + * "count" field, and should not look at table entries if + * it is 0. + * + * - All (synchronized) write operations should write to + * the "count" field after structurally changing any bin. + * The operations must not take any action that could even + * momentarily cause a concurrent read operation to see + * inconsistent data. This is made easier by the nature of + * the read operations in Map. For example, no operation + * can reveal that the table has grown but the threshold + * has not yet been updated, so there are no atomicity + * requirements for this with respect to reads. + * + * As a guide, all critical volatile reads and writes to the + * count field are marked in code comments. + */ + + /** The number of elements in this segment's region. */ + private transient volatile int cnt; + + /** + * Number of updates that alter the size of the table. This is + * used during bulk-read methods to make sure they see a + * consistent snapshot: If modCounts change during a traversal + * of segments computing size or checking containsValue, then + * we might have an inconsistent view of state so (usually) + * must retry. + */ + private transient int modCnt; + + /** + * The table is rehashed when its size exceeds this threshold. + * (The value of this field is always <tt>(int)(capacity * + * loadFactor)</tt>.) + */ + private transient int threshold; + + /** The per-segment table. */ + private transient volatile HashEntry<K, V>[] tbl; + + /** + * The load factor for the hash table. Even though this value + * is same for all segments, it is replicated to avoid needing + * links to outer object. + */ + private final float loadFactor; + + /** */ + private final Queue<HashEntry<K, V>> segEntryQ; + + /** + * @param initCap Segment initial capacity. + * @param loadFactor Segment load factor, + */ + Segment(int initCap, float loadFactor) { + this.loadFactor = loadFactor; + + segEntryQ = qPlc == PER_SEGMENT_Q ? new ArrayDeque<HashEntry<K, V>>() : + qPlc == PER_SEGMENT_Q_OPTIMIZED_RMV ? new ConcurrentLinkedDeque8<HashEntry<K, V>>() : null; + + setTable(HashEntry.<K, V>newArray(initCap)); + } + + /** + * Sets table to new HashEntry array. + * Call only while holding lock or in constructor. + * + * @param newTbl New hash table + */ + void setTable(HashEntry<K, V>[] newTbl) { + threshold = (int)(newTbl.length * loadFactor); + tbl = newTbl; + } + + /** + * Returns properly casted first entry of bin for given hash. + * + * @param hash Hash of the key. + * @return Head of bin's linked list. + */ + HashEntry<K, V> getFirst(int hash) { + HashEntry<K, V>[] tab = tbl; + + return tab[hash & (tab.length - 1)]; + } + + /** + * Reads value field of an entry under lock. Called if value + * field ever appears to be null. This is possible only if a + * compiler happens to reorder a HashEntry initialization with + * its table assignment, which is legal under memory model + * but is not known to ever occur. + * + * @param e Entry that needs to be read. + * @return Value of entry. + */ + V readValueUnderLock(HashEntry<K, V> e) { + readLock().lock(); + + try { + return e.val; + } + finally { + readLock().unlock(); + } + } + + /* Specialized implementations of map methods */ + + /** + * Performs lock-free read of value for given key. + * + * @param key Key to be read. + * @param hash Hash of the key + * @return Stored value + */ + V get(Object key, int hash) { + if (cnt != 0) { // read-volatile + HashEntry<K, V> e = getFirst(hash); + + while (e != null) { + if (e.hash == hash && key.equals(e.key)) { + V v = e.val; + + if (v != null) + return v; + + v = readValueUnderLock(e); + + return v; // recheck + } + + e = e.next; + } + } + + return null; + } + + /** + * Performs lock-based read of value for given key. + * In contrast with {@link #get(Object, int)} it is guaranteed + * to be consistent with order-based iterators. + * + * @param key Key to be read. + * @param hash Hash of the key + * @return Stored value + */ + V getSafe(Object key, int hash) { + readLock().lock(); + + try { + HashEntry<K, V> e = getFirst(hash); + + while (e != null) { + if (e.hash == hash && key.equals(e.key)) + return e.val; + + e = e.next; + } + + return null; + } + finally { + readLock().unlock(); + } + } + + /** + * Performs lock-free check of key presence. + * + * @param key Key to lookup. + * @param hash Hash of the key. + * @return {@code true} if segment contains this key. + */ + boolean containsKey(Object key, int hash) { + if (cnt != 0) { // read-volatile + HashEntry<K, V> e = getFirst(hash); + + while (e != null) { + if (e.hash == hash && key.equals(e.key)) + return true; + + e = e.next; + } + } + + return false; + } + + /** + * Performs lock-free check of value presence. + * + * @param val Value. + * @return {@code true} if segment contains this key. + */ + @SuppressWarnings("ForLoopReplaceableByForEach") + boolean containsValue(Object val) { + if (cnt != 0) { // read-volatile + HashEntry<K, V>[] tab = tbl; + + int len = tab.length; + + for (int i = 0 ; i < len; i++) { + for (HashEntry<K, V> e = tab[i]; e != null; e = e.next) { + V v = e.val; + + if (v == null) // recheck + v = readValueUnderLock(e); + + if (val.equals(v)) + return true; + } + } + } + + return false; + } + + /** + * Performs value replacement for a given key with old value check. + * + * @param key Key to replace. + * @param hash Hash of the key. + * @param oldVal Old value. + * @param newVal New value + * @return {@code true} If value was replaced. + */ + @SuppressWarnings({"unchecked"}) + boolean replace(K key, int hash, V oldVal, V newVal) { + writeLock().lock(); + + boolean replaced = false; + + try { + HashEntry<K, V> e = getFirst(hash); + + while (e != null && (e.hash != hash || !key.equals(e.key))) + e = e.next; + + if (e != null && oldVal.equals(e.val)) { + replaced = true; + + e.val = newVal; + } + } + finally { + writeLock().unlock(); + } + + return replaced; + } + + /** + * Performs value replacement for a given key with old value check. + * + * @param key Key to replace. + * @param hash Hash of the key. + * @param oldVal Old value. + * @param newVal New value + * @return {@code oldVal}, if value was replaced, non-null object if map + * contained some other value and {@code null} if there were no such key. + */ + @SuppressWarnings({"unchecked"}) + V replacex(K key, int hash, V oldVal, V newVal) { + writeLock().lock(); + + V replaced = null; + + try { + HashEntry<K, V> e = getFirst(hash); + + while (e != null && (e.hash != hash || !key.equals(e.key))) + e = e.next; + + if (e != null) { + if (oldVal.equals(e.val)) { + replaced = oldVal; + + e.val = newVal; + } + else + replaced = e.val; + } + } + finally { + writeLock().unlock(); + } + + return replaced; + } + + @SuppressWarnings({"unchecked"}) + V replace(K key, int hash, V newVal) { + writeLock().lock(); + + V oldVal = null; + + try { + HashEntry<K, V> e = getFirst(hash); + + while (e != null && (e.hash != hash || !key.equals(e.key))) + e = e.next; + + if (e != null) { + oldVal = e.val; + + e.val = newVal; + } + } + finally { + writeLock().unlock(); + } + + return oldVal; + } + + @SuppressWarnings({"unchecked"}) + V put(K key, int hash, V val, boolean onlyIfAbsent) { + writeLock().lock(); + + V oldVal; + + boolean added = false; + + try { + int c = cnt; + + if (c++ > threshold) // ensure capacity + rehash(); + + HashEntry<K, V>[] tab = tbl; + + int idx = hash & (tab.length - 1); + + HashEntry<K, V> first = tab[idx]; + + HashEntry<K, V> e = first; + + while (e != null && (e.hash != hash || !key.equals(e.key))) + e = e.next; + + boolean modified = false; + + if (e != null) { + oldVal = e.val; + + if (!onlyIfAbsent) { + e.val = val; + + modified = true; + } + } + else { + oldVal = null; + + ++modCnt; + + size.increment(); + + e = tab[idx] = new HashEntry<>(key, hash, first, val); + + ConcurrentLinkedHashMap.this.modCnt.increment(); + + e.modCnt = ConcurrentLinkedHashMap.this.modCnt.intValue(); + + cnt = c; // write-volatile + + added = true; + } + + assert !(added && modified); + + if (added) { + switch (qPlc) { + case PER_SEGMENT_Q_OPTIMIZED_RMV: + recordInsert(e, (ConcurrentLinkedDeque8)segEntryQ); + + if (maxCap > 0) + checkRemoveEldestEntrySegment(); + + break; + + case PER_SEGMENT_Q: + segEntryQ.add(e); + + if (maxCap > 0) + checkRemoveEldestEntrySegment(); + + break; + + default: + assert qPlc == SINGLE_Q; + + recordInsert(e, entryQ); + } + } + } + finally { + writeLock().unlock(); + } + + if (qPlc == SINGLE_Q && added && maxCap > 0) + checkRemoveEldestEntry(); + + return oldVal; + } + + /** + * + */ + private void checkRemoveEldestEntrySegment() { + assert maxCap > 0; + + int rmvCnt = sizex() - maxCap; + + for (int i = 0; i < rmvCnt; i++) { + HashEntry<K, V> e0 = segEntryQ.poll(); + + if (e0 == null) + break; + + removeLocked(e0.key, e0.hash, null /*no need to compare*/, false); + + if (sizex() <= maxCap) + break; + } + } + + /** + * This method is called under the segment lock. + */ + @SuppressWarnings({"ForLoopReplaceableByForEach", "unchecked"}) + void rehash() { + HashEntry<K, V>[] oldTbl = tbl; + int oldCap = oldTbl.length; + + if (oldCap >= MAX_CAP_LIMIT) + return; + + /* + * 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 with a power of two + * offset. We eliminate unnecessary node creation by catching + * cases where old nodes can be reused because their next + * fields won't change. Statistically, at the default + * threshold, only about one-sixth of them need cloning when + * a table doubles. 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. + */ + + int c = cnt; + + HashEntry<K, V>[] newTbl = HashEntry.newArray(oldCap << 1); + + threshold = (int)(newTbl.length * loadFactor); + + int sizeMask = newTbl.length - 1; + + for (int i = 0; i < oldCap; i++) { + // We need to guarantee that any existing reads of old Map can + // proceed. So we cannot yet null out each bin. + HashEntry<K, V> e = oldTbl[i]; + + if (e != null) { + HashEntry<K, V> next = e.next; + + int idx = e.hash & sizeMask; + + // Single node on list + if (next == null) + newTbl[idx] = e; + + else { + // Reuse trailing consecutive sequence at same slot + HashEntry<K, V> lastRun = e; + + int lastIdx = idx; + + for (HashEntry<K, V> last = next; last != null; last = last.next) { + int k = last.hash & sizeMask; + + if (k != lastIdx) { + lastIdx = k; + lastRun = last; + } + } + + newTbl[lastIdx] = lastRun; + + // Clone all remaining nodes + for (HashEntry<K, V> p = e; p != lastRun; p = p.next) { + int k = p.hash & sizeMask; + + HashEntry<K, V> n = newTbl[k]; + + HashEntry<K, V> e0 = new HashEntry<>(p.key, p.hash, n, p.val, p.node, p.modCnt); + + newTbl[k] = e0; + } + } + } + } + + cnt = c; + + tbl = newTbl; + } + + /** + * Remove; match on key only if value null, else match both. + * + * @param key Key to be removed. + * @param hash Hash of the key. + * @param val Value to match. + * @param cleanupQ {@code True} if need to cleanup queue. + * @return Old value, if entry existed, {@code null} otherwise. + */ + V remove(Object key, int hash, Object val, boolean cleanupQ) { + writeLock().lock(); + + try { + return removeLocked(key, hash, val, cleanupQ); + } + finally { + writeLock().unlock(); + } + } + + /** + * Locked version of remove. Match on key only if value null, else match both. + * + * @param key Key to be removed. + * @param hash Hash of the key. + * @param val Value to match. + * @param cleanupQ {@code True} if need to cleanup queue. + * @return Old value, if entry existed, {@code null} otherwise. + */ + @SuppressWarnings({"unchecked"}) + V removeLocked(Object key, int hash, Object val, boolean cleanupQ) { + int c = cnt - 1; + + HashEntry<K, V>[] tab = tbl; + + int idx = hash & (tab.length - 1); + + HashEntry<K, V> first = tab[idx]; + + HashEntry<K, V> e = first; + + while (e != null && (e.hash != hash || !key.equals(e.key))) + e = e.next; + + V oldVal = null; + + if (e != null) { + V v = e.val; + + if (val == null || val.equals(v)) { + oldVal = v; + + // All entries following removed node can stay + // in list, but all preceding ones need to be + // cloned. + ++modCnt; + + ConcurrentLinkedHashMap.this.modCnt.increment(); + + HashEntry<K, V> newFirst = e.next; + + for (HashEntry<K, V> p = first; p != e; p = p.next) + newFirst = new HashEntry<>(p.key, p.hash, newFirst, p.val, p.node, p.modCnt); + + tab[idx] = newFirst; + + cnt = c; // write-volatile + + size.decrement(); + } + } + + if (oldVal != null && cleanupQ) { + switch (qPlc) { + case PER_SEGMENT_Q_OPTIMIZED_RMV: + ((ConcurrentLinkedDeque8)segEntryQ).unlinkx(e.node); + + e.node = null; + + break; + + case PER_SEGMENT_Q: + // Linear time method call. + segEntryQ.remove(e); + + break; + + default: + assert qPlc == SINGLE_Q; + + entryQ.unlinkx(e.node); + + e.node = null; + } + } + + return oldVal; + } + + /** + * + */ + void clear() { + if (cnt != 0) { + writeLock().lock(); + + try { + HashEntry<K, V>[] tab = tbl; + + for (int i = 0; i < tab.length ; i++) + tab[i] = null; + + ++modCnt; + + cnt = 0; // write-volatile + } + finally { + writeLock().unlock(); + } + } + } + } + + /* ---------------- Public operations -------------- */ + + /** + * Creates a new, empty map with the specified initial + * capacity, load factor, concurrency level and max capacity. + * + * @param initCap the initial capacity. The implementation + * performs internal sizing to accommodate this many elements. + * @param loadFactor the load factor threshold, used to control resizing. + * Resizing may be performed when the average number of elements per + * bin exceeds this threshold. + * @param concurLvl the estimated number of concurrently + * updating threads. The implementation performs internal sizing + * to try to accommodate this many threads. + * @param maxCap Max capacity ({@code 0} for unbounded). + * @param qPlc Queue policy. + * @throws IllegalArgumentException if the initial capacity is + * negative or the load factor or concurLvl are + * non-positive. + */ + @SuppressWarnings({"unchecked"}) + public ConcurrentLinkedHashMap(int initCap, float loadFactor, int concurLvl, int maxCap, QueuePolicy qPlc) { + if (!(loadFactor > 0) || initCap < 0 || concurLvl <= 0) + throw new IllegalArgumentException(); + + if (concurLvl > MAX_SEGS) + concurLvl = MAX_SEGS; + + this.maxCap = maxCap; + this.qPlc = qPlc; + + entryQ = qPlc == SINGLE_Q ? new ConcurrentLinkedDeque8<HashEntry<K, V>>() : null; + + // Find power-of-two sizes best matching arguments + int sshift = 0; + + int ssize = 1; + + while (ssize < concurLvl) { + ++sshift; + ssize <<= 1; + } + + segmentShift = 32 - sshift; + + segmentMask = ssize - 1; + + segments = new Segment[ssize]; + + if (initCap > MAX_CAP_LIMIT) + initCap = MAX_CAP_LIMIT; + + int c = initCap / ssize; + + if (c * ssize < initCap) + ++c; + + int cap = 1; + + while (cap < c) + cap <<= 1; + + for (int i = 0; i < segments.length; ++i) + segments[i] = new Segment<>(cap, loadFactor); + } + + /** + * Creates a new, empty map with the specified initial + * capacity, load factor, concurrency level and max capacity. + * + * @param initCap the initial capacity. The implementation + * performs internal sizing to accommodate this many elements. + * @param loadFactor the load factor threshold, used to control resizing. + * Resizing may be performed when the average number of elements per + * bin exceeds this threshold. + * @param concurLvl the estimated number of concurrently + * updating threads. The implementation performs internal sizing + * to try to accommodate this many threads. + * @param maxCap Max capacity ({@code 0} for unbounded). + * @throws IllegalArgumentException if the initial capacity is + * negative or the load factor or concurLvl are + * non-positive. + */ + public ConcurrentLinkedHashMap(int initCap, float loadFactor, int concurLvl, int maxCap) { + this(initCap, loadFactor, concurLvl, maxCap, SINGLE_Q); + } + + /** + * Creates a new, empty map with the specified initial + * capacity, load factor and concurrency level. + * + * @param initCap the initial capacity. The implementation + * performs internal sizing to accommodate this many elements. + * @param loadFactor the load factor threshold, used to control resizing. + * Resizing may be performed when the average number of elements per + * bin exceeds this threshold. + * @param concurLvl the estimated number of concurrently + * updating threads. The implementation performs internal sizing + * to try to accommodate this many threads. + * @throws IllegalArgumentException if the initial capacity is + * negative or the load factor or concurLvl are + * non-positive. + */ + @SuppressWarnings({"unchecked"}) + public ConcurrentLinkedHashMap(int initCap, float loadFactor, int concurLvl) { + this(initCap, loadFactor, concurLvl, 0); + } + + /** + * Creates a new, empty map with the specified initial capacity + * and load factor and with the default concurrencyLevel (16). + * + * @param initCap The implementation performs internal + * sizing to accommodate this many elements. + * @param loadFactor the load factor threshold, used to control resizing. + * Resizing may be performed when the average number of elements per + * bin exceeds this threshold. + * @throws IllegalArgumentException if the initial capacity of + * elements is negative or the load factor is non-positive + * + * @since 1.6 + */ + public ConcurrentLinkedHashMap(int initCap, float loadFactor) { + this(initCap, loadFactor, DFLT_CONCUR_LVL); + } + + /** + * Creates a new, empty map with the specified initial capacity, + * and with default load factor (0.75) and concurrencyLevel (16). + * + * @param initCap the initial capacity. The implementation + * performs internal sizing to accommodate this many elements. + * @throws IllegalArgumentException if the initial capacity of + * elements is negative. + */ + public ConcurrentLinkedHashMap(int initCap) { + this(initCap, DFLT_LOAD_FACTOR, DFLT_CONCUR_LVL); + } + + /** + * Creates a new, empty map with a default initial capacity (16), + * load factor (0.75) and concurrencyLevel (16). + */ + public ConcurrentLinkedHashMap() { + this(DFLT_INIT_CAP, DFLT_LOAD_FACTOR, DFLT_CONCUR_LVL); + } + + /** + * Creates a new map with the same mappings as the given map. + * The map is created with a capacity of 1.5 times the number + * of mappings in the given map or 16 (whichever is greater), + * and a default load factor (0.75) and concurrencyLevel (16). + * + * @param m the map + */ + public ConcurrentLinkedHashMap(Map<? extends K, ? extends V> m) { + this(Math.max((int) (m.size() / DFLT_LOAD_FACTOR) + 1, DFLT_INIT_CAP), + DFLT_LOAD_FACTOR, DFLT_CONCUR_LVL); + + putAll(m); + } + + /** + * Returns <tt>true</tt> if this map contains no key-value mappings. + * + * @return <tt>true</tt> if this map contains no key-value mappings. + */ + @Override public boolean isEmpty() { + Segment<K, V>[] segments = this.segments; + /* + * We keep track of per-segment modCounts to avoid ABA + * problems in which an element in one segment was added and + * in another removed during traversal, in which case the + * table was never actually empty at any point. Note the + * similar use of modCounts in the size() and containsValue() + * methods, which are the only other methods also susceptible + * to ABA problems. + */ + int[] mc = new int[segments.length]; + int mcsum = 0; + + for (int i = 0; i < segments.length; ++i) { + if (segments[i].cnt != 0) + return false; + else + mcsum += mc[i] = segments[i].modCnt; + } + + // If mcsum happens to be zero, then we know we got a snapshot + // before any modifications at all were made. This is + // probably common enough to bother tracking. + if (mcsum != 0) { + for (int i = 0; i < segments.length; ++i) { + if (segments[i].cnt != 0 || + mc[i] != segments[i].modCnt) + return false; + } + } + + return true; + } + + /** + * Returns the number of key-value mappings in this map. If the + * map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns + * <tt>Integer.MAX_VALUE</tt>. + * + * @return the number of key-value mappings in this map + */ + @SuppressWarnings({"LockAcquiredButNotSafelyReleased"}) + @Override public int size() { + Segment<K, V>[] segments = this.segments; + long sum = 0; + long check = 0; + int[] mc = new int[segments.length]; + + // Try a few times to get accurate count. On failure due to + // continuous async changes in table, resort to locking. + for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) { + check = 0; + sum = 0; + int mcsum = 0; + + for (int i = 0; i < segments.length; ++i) { + sum += segments[i].cnt; + mcsum += mc[i] = segments[i].modCnt; + } + + if (mcsum != 0) { + for (int i = 0; i < segments.length; ++i) { + check += segments[i].cnt; + + if (mc[i] != segments[i].modCnt) { + check = -1; // force retry + + break; + } + } + } + + if (check == sum) + break; + } + + if (check != sum) { // Resort to locking all segments + sum = 0; + + for (Segment<K, V> segment : segments) + segment.readLock().lock(); + + for (Segment<K, V> segment : segments) + sum += segment.cnt; + + for (Segment<K, V> segment : segments) + segment.readLock().unlock(); + } + + return sum > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)sum; + } + + /** + * @return The number of key-value mappings in this map (constant-time). + */ + public int sizex() { + int i = size.intValue(); + + return i > 0 ? i : 0; + } + + /** + * @return <tt>true</tt> if this map contains no key-value mappings + */ + public boolean isEmptyx() { + return sizex() == 0; + } + + /** + * Returns the value to which the specified key is mapped, + * or {@code null} if this map contains no mapping for the key. + * + * <p>More formally, if this map contains a mapping from a key + * {@code k} to a value {@code v} such that {@code key.equals(k)}, + * then this method returns {@code v}; otherwise it returns + * {@code null}. (There can be at most one such mapping.) + * + * @throws NullPointerException if the specified key is null + */ + @Override public V get(Object key) { + int hash = hash(key.hashCode()); + + return segmentFor(hash).get(key, hash); + } + + /** + * Returns the value to which the specified key is mapped, + * or {@code null} if this map contains no mapping for the key. + * + * <p>More formally, if this map contains a mapping from a key + * {@code k} to a value {@code v} such that {@code key.equals(k)}, + * then this method returns {@code v}; otherwise it returns + * {@code null}. (There can be at most one such mapping.) + * + * In contrast with {@link #get(Object)} this method acquires + * read lock on segment where the key is mapped. + * + * @throws NullPointerException if the specified key is null + */ + public V getSafe(Object key) { + int hash = hash(key.hashCode()); + + return segmentFor(hash).getSafe(key, hash); + } + + /** + * Tests if the specified object is a key in this table. + * + * @param key possible key + * @return <tt>true</tt> if and only if the specified object + * is a key in this table, as determined by the + * <tt>equals</tt> method; <tt>false</tt> otherwise. + * @throws NullPointerException if the specified key is null + */ + @Override public boolean containsKey(Object key) { + int hash = hash(key.hashCode()); + + return segmentFor(hash).containsKey(key, hash); + } + + /** + * 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 val 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 + * @throws NullPointerException if the specified value is null + */ + @SuppressWarnings({"LockAcquiredButNotSafelyReleased"}) + @Override public boolean containsValue(Object val) { + if (val == null) + throw new NullPointerException(); + + // See explanation of modCount use above + + Segment<K, V>[] segments = this.segments; + int[] mc = new int[segments.length]; + + // Try a few times without locking + for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) { + int mcsum = 0; + + for (int i = 0; i < segments.length; ++i) { + mcsum += mc[i] = segments[i].modCnt; + + if (segments[i].containsValue(val)) + return true; + } + + boolean cleanSweep = true; + + if (mcsum != 0) { + for (int i = 0; i < segments.length; ++i) { + if (mc[i] != segments[i].modCnt) { + cleanSweep = false; + + break; + } + } + } + + if (cleanSweep) + return false; + } + + // Resort to locking all segments + for (Segment<K, V> segment : segments) + segment.readLock().lock(); + + boolean found = false; + + try { + for (Segment<K, V> segment : segments) { + if (segment.containsValue(val)) { + found = true; + + break; + } + } + } finally { + for (Segment<K, V> segment : segments) + segment.readLock().unlock(); + } + + return found; + } + + /** + * Legacy method testing if some key maps into the specified value + * in this table. This method is identical in functionality to + * {@link #containsValue}, and exists solely to ensure + * full compatibility with class {@link java.util.Hashtable}, + * which supported this method prior to introduction of the + * Java Collections framework. + + * @param val a value to search for + * @return <tt>true</tt> if and only if some key maps to the + * <tt>value</tt> argument in this table as + * determined by the <tt>equals</tt> method; + * <tt>false</tt> otherwise + * @throws NullPointerException if the specified value is null + */ + public boolean contains(Object val) { + return containsValue(val); + } + + /** + * Maps the specified key to the specified value in this table. + * Neither the key nor the value can be null. + * + * <p> The value can be retrieved by calling the <tt>get</tt> method + * with a key that is equal to the original key. + * + * @param key key with which the specified value is to be associated + * @param val value to be associated with the specified key + * @return the previous value associated with <tt>key</tt>, or + * <tt>null</tt> if there was no mapping for <tt>key</tt> + * @throws NullPointerException if the specified key or value is null + */ + @Override public V put(K key, V val) { + if (val == null) + throw new NullPointerException(); + + int hash = hash(key.hashCode()); + + return segmentFor(hash).put(key, hash, val, false); + } + + /** + * {@inheritDoc} + * + * @return the previous value associated with the specified key, + * or <tt>null</tt> if there was no mapping for the key + * @throws NullPointerException if the specified key or value is null + */ + @Override public V putIfAbsent(K key, V val) { + if (val == null) + throw new NullPointerException(); + + int hash = hash(key.hashCode()); + + return segmentFor(hash).put(key, hash, val, 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 + */ + @Override public void putAll(Map<? extends K, ? extends V> m) { + for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) + put(e.getKey(), e.getValue()); + } + + /** + * Removes the key (and its corresponding value) from this map. + * This method does nothing if the key is not in the map. + * + * @param key the key that needs to be removed + * @return the previous value associated with <tt>key</tt>, or + * <tt>null</tt> if there was no mapping for <tt>key</tt> + * @throws NullPointerException if the specified key is null + */ + @Override public V remove(Object key) { + int hash = hash(key.hashCode()); + + return segmentFor(hash).remove(key, hash, null, true); + } + + /** + * {@inheritDoc} + * + * @throws NullPointerException if the specified key is null + */ + @SuppressWarnings("NullableProblems") + @Override public boolean remove(Object key, Object val) { + int hash = hash(key.hashCode()); + + return val != null && segmentFor(hash).remove(key, hash, val, true) != null; + } + + /** + * {@inheritDoc} + * + * @throws NullPointerException if any of the arguments are null + */ + @SuppressWarnings("NullableProblems") + @Override public boolean replace(K key, V oldVal, V newVal) { + if (oldVal == null || newVal == null) + throw new NullPointerException(); + + int hash = hash(key.hashCode()); + + return segmentFor(hash).replace(key, hash, oldVal, newVal); + } + + /** + * Replaces the entry for a key only if currently mapped to a given value. + * This is equivalent to + * <pre> + * if (map.containsKey(key)) { + * if (map.get(key).equals(oldValue)) { + * map.put(key, newValue); + * return oldValue; + * } else + * return map.get(key); + * } else return null;</pre> + * except that the action is performed atomically. + * + * @param key key with which the specified value is associated + * @param oldVal value expected to be associated with the specified key + * @param newVal value to be associated with the specified key + * @return {@code oldVal}, if value was replaced, non-null previous value if map + * contained some other value and {@code null} if there were no such key. + */ + public V replacex(K key, V oldVal, V newVal) { + if (oldVal == null || newVal == null) + throw new NullPointerException(); + + int hash = hash(key.hashCode()); + + return segmentFor(hash).replacex(key, hash, oldVal, newVal); + } + + /** + * {@inheritDoc} + * + * @return the previous value associated with the specified key, + * or <tt>null</tt> if there was no mapping for the key + * @throws NullPointerException if the specified key or value is null + */ + @SuppressWarnings("NullableProblems") + @Override public V replace(K key, V val) { + if (val == null) + throw new NullPointerException(); + + int hash = hash(key.hashCode()); + + return segmentFor(hash).replace(key, hash, val); + } + + /** + * Removes all of the mappings from this map. + */ + @Override public void clear() { + for (Segment<K, V> segment : segments) + segment.clear(); + } + + /** + * Returns a {@link 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. + * + * <p>The view's <tt>iterator</tt> 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) + * reflect any modifications subsequent to construction. + */ + @Override public Set<K> keySet() { + Set<K> ks = keySet; + + return (ks != null) ? ks : (keySet = new KeySet()); + } + + /** + * Returns a {@link Set} view of the keys contained in this map + * in descending order. + * 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. + * + * <p>The view's <tt>iterator</tt> 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) + * reflect any modifications subsequent to construction. + */ + public Set<K> descendingKeySet() { + Set<K> ks = descKeySet; + + return (ks != null) ? ks : (descKeySet = new KeySetDescending()); + } + + /** + * Returns a {@link 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. + * + * <p>The view's <tt>iterator</tt> 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) + * reflect any modifications subsequent to construction. + */ + @Override public Collection<V> values() { + Collection<V> vs = vals; + + return (vs != null) ? vs : (vals = new Values()); + } + + /** + * Returns a {@link Collection} view of the values contained in this map + * in descending order. + * 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. + * + * <p>The view's <tt>iterator</tt> 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) + * reflect any modifications subsequent to construction. + */ + public Collection<V> descendingValues() { + Collection<V> vs = descVals; + + return (vs != null) ? vs : (descVals = new ValuesDescending()); + } + + /** + * Returns a {@link Set} view of the mappings 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 the 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. + * + * <p>The view's <tt>iterator</tt> 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) + * reflect any modifications subsequent to construction. + */ + @Override public Set<Map.Entry<K, V>> entrySet() { + Set<Map.Entry<K, V>> es = entrySet; + + return (es != null) ? es : (entrySet = new EntrySet()); + } + + /** + * Returns a {@link Set} view of the mappings contained in this map + * in descending order. + * 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 the 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. + * + * <p>The view's <tt>iterator</tt> 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) + * reflect any modifications subsequent to construction. + */ + public Set<Map.Entry<K, V>> descendingEntrySet() { + Set<Map.Entry<K, V>> es = descEntrySet; + + return (es != null) ? es : (descEntrySet = new EntrySetDescending()); + } + + /** + * Returns an enumeration of the keys in this table. + * + * @return an enumeration of the keys in this table. + * @see #keySet() + */ + public Enumeration<K> keys() { + return new KeyIterator(true); + } + + /** + * Returns an enumeration of the keys in this table in descending order. + * + * @return an enumeration of the keys in this table in descending order. + * @see #keySet() + */ + public Enumeration<K> descendingKeys() { + return new KeyIterator(false); + } + + /** + * Returns an enumeration of the values in this table. + * + * @return an enumeration of the values in this table. + * @see #values() + */ + public Enumeration<V> elements() { + return new ValueIterator(true); + } + + /** + * Returns an enumeration of the values in this table in descending order. + * + * @return an enumeration of the values in this table in descending order. + * @see #values() + */ + public Enumeration<V> descendingElements() { + return new ValueIterator(false); + } + + /** + * This method is called by hash map whenever a new entry is inserted into map. + * <p> + * This method is called outside the segment-protection lock and may be called concurrently. + * + * @param e The new inserted entry. + */ + @SuppressWarnings({"unchecked"}) + private void recordInsert(HashEntry e, ConcurrentLinkedDeque8 q) { + e.node = q.addx(e); + } + + /** + * Concurrently removes eldest entry from the map. + */ + private void checkRemoveEldestEntry() { + assert maxCap > 0; + assert qPlc == SINGLE_Q; + + int sizex = sizex(); + + for (int i = maxCap; i < sizex; i++) { + HashEntry<K, V> e = entryQ.poll(); + + if (e != null) + segmentFor(e.hash).remove(e.key, e.hash, e.val, false); + else + return; + + if (sizex() <= maxCap) + return; + } + } + + /** + * This method is intended for test purposes only. + * + * @return Queue. + */ + public ConcurrentLinkedDeque8<HashEntry<K, V>> queue() { + return entryQ; + } + + /** + * @return Queue policy. + */ + public QueuePolicy policy() { + return qPlc; + } + + /** + * Class implementing iteration over map entries. + */ + private abstract class HashIterator { + /** Underlying collection iterator. */ + private Iterator<HashEntry<K, V>> delegate; + + /** Last returned entry, used in {@link #remove()} method. */ + private HashEntry<K, V> lastReturned; + + /** Next entry to return */ + private HashEntry<K, V> nextEntry; + + /** The map modification count at the creation time. */ + private int modCnt; + + /** + * @param asc {@code True} for ascending iterator. + */ + HashIterator(boolean asc) { + // TODO GG-4788 - Need to fix iterators for ConcurrentLinkedHashMap in perSegment mode + if (qPlc != SINGLE_Q) + throw new IllegalStateException("Iterators are not supported in 'perSegmentQueue' modes."); + + modCnt = ConcurrentLinkedHashMap.this.modCnt.intValue(); + + // Init delegate. + delegate = asc ? entryQ.iterator() : entryQ.descendingIterator(); + + advance(); + } + + /** + * @return Copy of the queue. + */ + private Deque<HashEntry<K, V>> copyQueue() { + int i = entryQ.sizex(); + + Deque<HashEntry<K, V>> res = new ArrayDeque<>(i); + + Iterator<HashEntry<K, V>> iter = entryQ.iterator(); + + while (iter.hasNext() && i-- >= 0) + res.add(iter.next()); + + assert !iter.hasNext() : "Entries queue has been modified."; + + return res; + } + + /** + * @return {@code true} If iterator has elements to iterate. + */ + public boolean hasMoreElements() { + return hasNext(); + } + + /** + * @return {@code true} If iterator has elements to iterate. + */ + public boolean hasNext() { + return nextEntry != null; + } + + /** + * @return Next entry. + */ + HashEntry<K, V> nextEntry() { + if (nextEntry == null) + throw new NoSuchElementException(); + + lastReturned = nextEntry; + + advance(); + + return lastReturned; + } + + /** + * Removes entry returned by {@link #nextEntry()}. + */ + public void remove() { + if (lastReturned == null) + throw new IllegalStateException(); + + ConcurrentLinkedHashMap.this.remove(lastReturned.key); + + lastReturned = null; + } + + /** + * Moves iterator to the next position. + */ + private void advance() { + nextEntry = null; + + while (delegate.hasNext()) { + HashEntry<K, V> n = delegate.next(); + + if (n.modCnt <= modCnt) { + nextEntry = n; + + break; + } + } + } + } + + /** + * Key iterator implementation. + */ + private final class KeyIterator extends HashIterator implements Iterator<K>, Enumeration<K> { + /** + * @param asc {@code True} for ascending iterator. + */ + private KeyIterator(boolean asc) { + super(asc); + } + + /** {@inheritDoc} */ + @Override public K next() { + return nextEntry().key; + } + + /** {@inheritDoc} */ + @Override public K nextElement() { + return nextEntry().key; + } + } + + /** + * Value iterator implementation. + */ + private final class ValueIterator extends HashIterator implements Iterator<V>, Enumeration<V> { + /** + * @param asc {@code True} for ascending iterator. + */ + private ValueIterator(boolean asc) { + super(asc); + } + + /** {@inheritDoc} */ + @Override public V next() { + return nextEntry().val; + } + + /** {@inheritDoc} */ + @Override public V nextElement() { + return nextEntry().val; + } + } + + /** + * Custom Entry class used by EntryIterator.next(), that relays + * setValue changes to the underlying map. + */ + private final class WriteThroughEntry extends AbstractMap.SimpleEntry<K, V> { + /** + * @param k Key + * @param v Value + */ + WriteThroughEntry(K k, V v) { + super(k,v); + } + + /** + * Set our entry's value and write through to the map. The + * value to return is somewhat arbitrary here. Since a + * WriteThroughEntry does not necessarily track asynchronous + * changes, the most recent "previous" value could be + * different from what we return (or could even have been + * removed in which case the put will re-establish). We do not + * and cannot guarantee more. + */ + @Override public V setValue(V val) { + if (val == null) + throw new NullPointerException(); + + V v = super.setValue(val); + + put(getKey(), val); + + return v; + } + } + + /** + * Entry iterator implementation. + */ + private final class EntryIterator extends HashIterator implements Iterator<Entry<K, V>> { + /** + * @param asc {@code True} for ascending iterator. + */ + private EntryIterator(boolean asc) { + super(asc); + } + + /** {@inheritDoc} */ + @Override public Map.Entry<K, V> next() { + HashEntry<K, V> e = nextEntry(); + + return new WriteThroughEntry(e.key, e.val); + } + } + + /** + * Key set of the map. + */ + private abstract class AbstractKeySet extends AbstractSet<K> { + /** {@inheritDoc} */ + @Override public int size() { + return ConcurrentLinkedHashMap.this.size(); + } + + /** {@inheritDoc} */ + @Override public boolean contains(Object o) { + return containsKey(o); + } + + /** {@inheritDoc} */ + @Override public boolean remove(Object o) { + return ConcurrentLinkedHashMap.this.remove(o) != null; + } + + /** {@inheritDoc} */ + @Override public void clear() { + ConcurrentLinkedHashMap.this.clear(); + } + } + + /** + * Key set of the map. + */ + private final class KeySet extends AbstractKeySet { + /** {@inheritDoc} */ + @Override public Iterator<K> iterator() { + return new KeyIterator(true); + } + } + + /** + * Key set of the map. + */ + private final class KeySetDescending extends AbstractKeySet { + /** {@inheritDoc} */ + @Override public Iterator<K> iterator() { + return new KeyIterator(false); + } + } + + /** + * Values collection of the map. + */ + private abstract class AbstractValues extends AbstractCollection<V> { + /** {@inheritDoc} */ + @Override public int size() { + return ConcurrentLinkedHashMap.this.size(); + } + + /** {@inheritDoc} */ + @Override public boolean contains(Object o) { + return containsValue(o); + } + + /** {@inheritDoc} */ + @Override public void clear() { + ConcurrentLinkedHashMap.this.clear(); + } + } + + /** + * Values collection of the map. + */ + private final class Values extends AbstractValues { + /** {@inheritDoc} */ + @Override public Iterator<V> iterator() { + return new ValueIterator(true); + } + } + + /** + * Values collection of the map. + */ + private final class ValuesDescending extends AbstractValues { + /** {@inheritDoc} */ + @Override public Iterator<V> iterator() { + return new ValueIterator(false); + } + } + + /** + * Entry set implementation. + */ + private abstract class AbstractEntrySet extends AbstractSet<Map.Entry<K, V>> { + /** {@inheritDoc} */ + @Override public boolean contains(Object o) { + if (!(o instanceof Map.Entry)) + return false; + + Map.Entry<?,?> e = (Map.Entry<?,?>)o; + + V v = get(e.getKey()); + + return v != null && v.equals(e.getValue()); + } + + /** {@inheritDoc} */ + @Override public boolean remove(Object o) { + if (!(o instanceof Map.Entry)) + return false; + + Map.Entry<?,?> e = (Map.Entry<?,?>)o; + + return ConcurrentLinkedHashMap.this.remove(e.getKey(), e.getValue()); + } + + /** {@inheritDoc} */ + @Override public int size() { + return ConcurrentLinkedHashMap.this.size(); + } + + /** {@inheritDoc} */ + @Override public void clear() { + ConcurrentLinkedHashMap.this.clear(); + } + } + + /** + * Entry set implementation. + */ + private final class EntrySet extends AbstractEntrySet { + /** {@inheritDoc} */ + @Override public Iterator<Map.Entry<K, V>> iterator() { + return new EntryIterator(true); + } + } + + /** + * Entry set implementation. + */ + private final class EntrySetDescending extends AbstractEntrySet { + /** {@inheritDoc} */ + @Override public Iterator<Map.Entry<K, V>> iterator() { + return new EntryIterator(false); + } + } + + /** + * Defines queue policy for this hash map. + */ + @SuppressWarnings("PublicInnerClass") + public enum QueuePolicy { + /** + * Default policy. Single queue is maintained. Iteration order is preserved. + */ + SINGLE_Q, + + /** + * Instance of {@code ArrayDeque} is created for each segment. This gives + * the fastest "natural" evicts for bounded maps. + * <p> + * NOTE: Remove operations on map are slower than with other policies. + */ + PER_SEGMENT_Q, + + /** + * Instance of {@code GridConcurrentLinkedDequeue} is created for each segment. This gives + * faster "natural" evicts for bounded queues and better remove operation times. + */ + PER_SEGMENT_Q_OPTIMIZED_RMV + } +}
http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1e649dc/modules/core/src/main/java/org/jdk8/backport/LongAdder.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/jdk8/backport/LongAdder.java b/modules/core/src/main/java/org/jdk8/backport/LongAdder.java new file mode 100644 index 0000000..1460b4c --- /dev/null +++ b/modules/core/src/main/java/org/jdk8/backport/LongAdder.java @@ -0,0 +1,235 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. Oracle designates this + * particular file as subject to the "Classpath" exception as provided + * by Oracle in the LICENSE file that accompanied this code. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ + +/* + * This file is available under and governed by the GNU General Public + * License version 2 only, as published by the Free Software Foundation. + * However, the following notice accompanied the original version of this + * file: + * + * 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/ + */ + +/* + * Copyright © 1993, 2013, Oracle and/or its affiliates. + * All rights reserved. + */ + +package org.jdk8.backport; + +import java.io.*; +import java.util.concurrent.atomic.*; + +/** + * One or more variables that together maintain an initially zero + * {@code long} sum. When updates (method {@link #add}) are contended + * across threads, the set of variables may grow dynamically to reduce + * contention. Method {@link #sum} (or, equivalently, {@link + * #longValue}) returns the current total combined across the + * variables maintaining the sum. + * + * <p> This class is usually preferable to {@link AtomicLong} when + * multiple threads update a common sum that is used for purposes such + * as collecting statistics, not for fine-grained synchronization + * control. Under low update contention, the two classes have similar + * characteristics. But under high contention, expected throughput of + * this class is significantly higher, at the expense of higher space + * consumption. + * + * <p>This class extends {@link Number}, but does <em>not</em> define + * methods such as {@code hashCode} and {@code compareTo} because + * instances are expected to be mutated, and so are not useful as + * collection keys. + * + * <p><em>jsr166e note: This class is targeted to be placed in + * java.util.concurrent.atomic<em> + * + * @since 1.8 + * @author Doug Lea + */ +@SuppressWarnings("ALL") +public class LongAdder extends Striped64 implements Serializable { + private static final long serialVersionUID = 7249069246863182397L; + + /** + * Version of plus for use in retryUpdate + */ + final long fn(long v, long x) { return v + x; } + + /** + * Creates a new adder with initial sum of zero. + */ + public LongAdder() { + } + + /** + * Adds the given value. + * + * @param x the value to add + */ + public void add(long x) { + Cell[] as; long b, v; HashCode hc; Cell a; int n; + if ((as = cells) != null || !casBase(b = base, b + x)) { + boolean uncontended = true; + int h = (hc = threadHashCode.get()).code; + if (as == null || (n = as.length) < 1 || + (a = as[(n - 1) & h]) == null || + !(uncontended = a.cas(v = a.value, v + x))) + retryUpdate(x, hc, uncontended); + } + } + + /** + * Equivalent to {@code add(1)}. + */ + public void increment() { + add(1L); + } + + /** + * Equivalent to {@code add(-1)}. + */ + public void decrement() { + add(-1L); + } + + /** + * Returns the current sum. The returned value is <em>NOT</em> an + * atomic snapshot: Invocation in the absence of concurrent + * updates returns an accurate result, but concurrent updates that + * occur while the sum is being calculated might not be + * incorporated. + * + * @return the sum + */ + public long sum() { + long sum = base; + Cell[] as = cells; + if (as != null) { + int n = as.length; + for (int i = 0; i < n; ++i) { + Cell a = as[i]; + if (a != null) + sum += a.value; + } + } + return sum; + } + + /** + * Resets variables maintaining the sum to zero. This method may + * be a useful alternative to creating a new adder, but is only + * effective if there are no concurrent updates. Because this + * method is intrinsically racy, it should only be used when it is + * known that no threads are concurrently updating. + */ + public void reset() { + internalReset(0L); + } + + /** + * Equivalent in effect to {@link #sum} followed by {@link + * #reset}. This method may apply for example during quiescent + * points between multithreaded computations. If there are + * updates concurrent with this method, the returned value is + * <em>not</em> guaranteed to be the final value occurring before + * the reset. + * + * @return the sum + */ + public long sumThenReset() { + long sum = base; + Cell[] as = cells; + base = 0L; + if (as != null) { + int n = as.length; + for (int i = 0; i < n; ++i) { + Cell a = as[i]; + if (a != null) { + sum += a.value; + a.value = 0L; + } + } + } + return sum; + } + + /** + * Equivalent to {@link #sum}. + * + * @return the sum + */ + public long longValue() { + return sum(); + } + + /** + * Returns the {@link #sum} as an {@code int} after a narrowing + * primitive conversion. + */ + public int intValue() { + return (int)sum(); + } + + /** + * Returns the {@link #sum} as a {@code float} + * after a widening primitive conversion. + */ + public float floatValue() { + return (float)sum(); + } + + /** + * Returns the {@link #sum} as a {@code double} after a widening + * primitive conversion. + */ + public double doubleValue() { + return (double)sum(); + } + + private void writeObject(java.io.ObjectOutputStream s) + throws java.io.IOException { + s.defaultWriteObject(); + s.writeLong(sum()); + } + + private void readObject(ObjectInputStream s) + throws IOException, ClassNotFoundException { + s.defaultReadObject(); + busy = 0; + cells = null; + base = s.readLong(); + } + + /** + * Returns the String representation of the {@link #sum}. + * + * @return String representation of the {@link #sum} + */ + public String toString() { + return Long.toString(sum()); + } +}
