/*
* 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 java.util.concurrent;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.CountedCompleter;
import java.util.Spliterator;
import java.util.stream.Stream;
import java.util.stream.Streams;
import java.util.function.*;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.function.BiFunction;
import java.util.Comparator;
import java.util.Arrays;
import java.util.Map;
import java.util.Set;
import java.util.Collection;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.AbstractCollection;
import java.util.Hashtable;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Enumeration;
import java.util.ConcurrentModificationException;
import java.util.NoSuchElementException;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.locks.AbstractQueuedSynchronizer;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;
import java.io.Serializable;
import java.lang.reflect.Type;
import java.lang.reflect.ParameterizedType;
/**
* A hash table supporting full concurrency of retrievals and
* high 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
* {@code Hashtable}. However, even though all operations are
* thread-safe, retrieval operations do not entail locking,
* and there is not any support for locking the entire table
* in a way that prevents all access. This class is fully
* interoperable with {@code Hashtable} in programs that rely on its
* thread safety but not on its synchronization details.
*
*
Retrieval operations (including {@code get}) generally do not
* block, so may overlap with update operations (including {@code put}
* and {@code remove}). Retrievals reflect the results of the most
* recently completed update operations holding upon their
* onset. (More formally, an update operation for a given key bears a
* happens-before relation with any (non-null) retrieval for
* that key reporting the updated value.) For aggregate operations
* such as {@code putAll} and {@code clear}, 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 not throw {@link
* ConcurrentModificationException}. However, iterators are designed
* to be used by only one thread at a time. Bear in mind that the
* results of aggregate status methods including {@code size}, {@code
* isEmpty}, and {@code containsValue} are typically useful only when
* a map is not undergoing concurrent updates in other threads.
* Otherwise the results of these methods reflect transient states
* that may be adequate for monitoring or estimation purposes, but not
* for program control.
*
*
The table is dynamically expanded when there are too many
* collisions (i.e., keys that have distinct hash codes but fall into
* the same slot modulo the table size), with the expected average
* effect of maintaining roughly two bins per mapping (corresponding
* to a 0.75 load factor threshold for resizing). There may be much
* variance around this average as mappings are added and removed, but
* overall, this maintains a commonly accepted time/space tradeoff for
* hash tables. However, resizing this or any other kind of hash
* table may be a relatively slow operation. When possible, it is a
* good idea to provide a size estimate as an optional {@code
* initialCapacity} constructor argument. An additional optional
* {@code loadFactor} constructor argument provides a further means of
* customizing initial table capacity by specifying the table density
* to be used in calculating the amount of space to allocate for the
* given number of elements. Also, for compatibility with previous
* versions of this class, constructors may optionally specify an
* expected {@code concurrencyLevel} as an additional hint for
* internal sizing. Note that using many keys with exactly the same
* {@code hashCode()} is a sure way to slow down performance of any
* hash table.
*
*
A {@link Set} projection of a ConcurrentHashMap may be created
* (using {@link #newKeySet()} or {@link #newKeySet(int)}), or viewed
* (using {@link #keySet(Object)} when only keys are of interest, and the
* mapped values are (perhaps transiently) not used or all take the
* same mapping value.
*
*
A ConcurrentHashMap can be used as scalable frequency map (a
* form of histogram or multiset) by using {@link
* java.util.concurrent.atomic.LongAdder} values and initializing via
* {@link #computeIfAbsent computeIfAbsent}. For example, to add a count
* to a {@code ConcurrentHashMap freqs}, you can use
* {@code freqs.computeIfAbsent(k -> new LongAdder()).increment();}
*
*
This class and its views and iterators implement all of the
* optional methods of the {@link Map} and {@link Iterator}
* interfaces.
*
*
Like {@link Hashtable} but unlike {@link HashMap}, this class
* does not allow {@code null} to be used as a key or value.
*
*
ConcurrentHashMaps support sequential and parallel operations
* bulk operations. (Parallel forms use the {@link
* ForkJoinPool#commonPool()}). Tasks that may be used in other
* contexts are available in class {@link ForkJoinTasks}. These
* operations are designed to be safely, and often sensibly, applied
* even with maps that are being concurrently updated by other
* threads; for example, when computing a snapshot summary of the
* values in a shared registry. There are three kinds of operation,
* each with four forms, accepting functions with Keys, Values,
* Entries, and (Key, Value) arguments and/or return values. Because
* the elements of a ConcurrentHashMap are not ordered in any
* particular way, and may be processed in different orders in
* different parallel executions, the correctness of supplied
* functions should not depend on any ordering, or on any other
* objects or values that may transiently change while computation is
* in progress; and except for forEach actions, should ideally be
* side-effect-free.
*
*
*
forEach: Perform a given action on each element.
* A variant form applies a given transformation on each element
* before performing the action.
*
*
search: Return the first available non-null result of
* applying a given function on each element; skipping further
* search when a result is found.
*
*
reduce: Accumulate each element. The supplied reduction
* function cannot rely on ordering (more formally, it should be
* both associative and commutative). There are five variants:
*
*
*
*
Plain reductions. (There is not a form of this method for
* (key, value) function arguments since there is no corresponding
* return type.)
*
*
Mapped reductions that accumulate the results of a given
* function applied to each element.
*
*
Reductions to scalar doubles, longs, and ints, using a
* given basis value.
*
*
*
*
*
*
The concurrency properties of bulk operations follow
* from those of ConcurrentHashMap: Any non-null result returned
* from {@code get(key)} and related access methods bears a
* happens-before relation with the associated insertion or
* update. The result of any bulk operation reflects the
* composition of these per-element relations (but is not
* necessarily atomic with respect to the map as a whole unless it
* is somehow known to be quiescent). Conversely, because keys
* and values in the map are never null, null serves as a reliable
* atomic indicator of the current lack of any result. To
* maintain this property, null serves as an implicit basis for
* all non-scalar reduction operations. For the double, long, and
* int versions, the basis should be one that, when combined with
* any other value, returns that other value (more formally, it
* should be the identity element for the reduction). Most common
* reductions have these properties; for example, computing a sum
* with basis 0 or a minimum with basis MAX_VALUE.
*
*
Search and transformation functions provided as arguments
* should similarly return null to indicate the lack of any result
* (in which case it is not used). In the case of mapped
* reductions, this also enables transformations to serve as
* filters, returning null (or, in the case of primitive
* specializations, the identity basis) if the element should not
* be combined. You can create compound transformations and
* filterings by composing them yourself under this "null means
* there is nothing there now" rule before using them in search or
* reduce operations.
*
*
Methods accepting and/or returning Entry arguments maintain
* key-value associations. They may be useful for example when
* finding the key for the greatest value. Note that "plain" Entry
* arguments can be supplied using {@code new
* AbstractMap.SimpleEntry(k,v)}.
*
*
Bulk operations may complete abruptly, throwing an
* exception encountered in the application of a supplied
* function. Bear in mind when handling such exceptions that other
* concurrently executing functions could also have thrown
* exceptions, or would have done so if the first exception had
* not occurred.
*
*
Speedups for parallel compared to sequential forms are common
* but not guaranteed. Parallel operations involving brief functions
* on small maps may execute more slowly than sequential forms if the
* underlying work to parallelize the computation is more expensive
* than the computation itself. Similarly, parallelization may not
* lead to much actual parallelism if all processors are busy
* performing unrelated tasks.
*
*
All arguments to all task methods must be non-null.
*
*
This class is a member of the
*
* Java Collections Framework.
*
* @since 1.5
* @author Doug Lea
* @param the type of keys maintained by this map
* @param the type of mapped values
*/
public class ConcurrentHashMap
implements ConcurrentMap, Serializable {
private static final long serialVersionUID = 7249069246763182397L;
/*
* Overview:
*
* The primary design goal of this hash table is to maintain
* concurrent readability (typically method get(), but also
* iterators and related methods) while minimizing update
* contention. Secondary goals are to keep space consumption about
* the same or better than java.util.HashMap, and to support high
* initial insertion rates on an empty table by many threads.
*
* Each key-value mapping is held in a Node. Because Node key
* fields can contain special values, they are defined using plain
* Object types (not type "K"). This leads to a lot of explicit
* casting (and many explicit warning suppressions to tell
* compilers not to complain about it). It also allows some of the
* public methods to be factored into a smaller number of internal
* methods (although sadly not so for the five variants of
* put-related operations). The validation-based approach
* explained below leads to a lot of code sprawl because
* retry-control precludes factoring into smaller methods.
*
* The table is lazily initialized to a power-of-two size upon the
* first insertion. Each bin in the table normally contains a
* list of Nodes (most often, the list has only zero or one Node).
* Table accesses require volatile/atomic reads, writes, and
* CASes. Because there is no other way to arrange this without
* adding further indirections, we use intrinsics
* (sun.misc.Unsafe) operations. The lists of nodes within bins
* are always accurately traversable under volatile reads, so long
* as lookups check hash code and non-nullness of value before
* checking key equality.
*
* We use the top (sign) bit of Node hash fields for control
* purposes -- it is available anyway because of addressing
* constraints. Nodes with negative hash fields are forwarding
* nodes to either TreeBins or resized tables. The lower 31 bits
* of each normal Node's hash field contain a transformation of
* the key's hash code.
*
* Insertion (via put or its variants) of the first node in an
* empty bin is performed by just CASing it to the bin. This is
* by far the most common case for put operations under most
* key/hash distributions. Other update operations (insert,
* delete, and replace) require locks. We do not want to waste
* the space required to associate a distinct lock object with
* each bin, so instead use the first node of a bin list itself as
* a lock. Locking support for these locks relies on builtin
* "synchronized" monitors.
*
* Using the first node of a list as a lock does not by itself
* suffice though: When a node is locked, any update must first
* validate that it is still the first node after locking it, and
* retry if not. Because new nodes are always appended to lists,
* once a node is first in a bin, it remains first until deleted
* or the bin becomes invalidated (upon resizing). However,
* operations that only conditionally update may inspect nodes
* until the point of update. This is a converse of sorts to the
* lazy locking technique described by Herlihy & Shavit.
*
* The main disadvantage of per-bin locks is that other update
* operations on other nodes in a bin list protected by the same
* lock can stall, for example when user equals() or mapping
* functions take a long time. However, statistically, under
* random hash codes, this is not a common problem. Ideally, the
* frequency of nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average, given the resizing threshold
* of 0.75, although with a large variance because of resizing
* granularity. Ignoring variance, the expected occurrences of
* list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The
* first values are:
*
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million
*
* Lock contention probability for two threads accessing distinct
* elements is roughly 1 / (8 * #elements) under random hashes.
*
* Actual hash code distributions encountered in practice
* sometimes deviate significantly from uniform randomness. This
* includes the case when N > (1<<30), so some keys MUST collide.
* Similarly for dumb or hostile usages in which multiple keys are
* designed to have identical hash codes. Also, although we guard
* against the worst effects of this (see method spread), sets of
* hashes may differ only in bits that do not impact their bin
* index for a given power-of-two mask. So we use a secondary
* strategy that applies when the number of nodes in a bin exceeds
* a threshold, and at least one of the keys implements
* Comparable. These TreeBins use a balanced tree to hold nodes
* (a specialized form of red-black trees), bounding search time
* to O(log N). Each search step in a TreeBin is around twice as
* slow as in a regular list, but given that N cannot exceed
* (1<<64) (before running out of addresses) this bounds search
* steps, lock hold times, etc, to reasonable constants (roughly
* 100 nodes inspected per operation worst case) so long as keys
* are Comparable (which is very common -- String, Long, etc).
* TreeBin nodes (TreeNodes) also maintain the same "next"
* traversal pointers as regular nodes, so can be traversed in
* iterators in the same way.
*
* The table is resized when occupancy exceeds a percentage
* threshold (nominally, 0.75, but see below). Any thread
* noticing an overfull bin may assist in resizing after the
* initiating thread allocates and sets up the replacement
* array. However, rather than stalling, these other threads may
* proceed with insertions etc. The use of TreeBins shields us
* from the worst case effects of overfilling while resizes are in
* progress. Resizing proceeds by transferring bins, one by one,
* from the table to the next table. To enable concurrency, the
* next table must be (incrementally) prefilled with place-holders
* serving as reverse forwarders to the old table. 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. On average, 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 concurrently
* traversing table. Upon transfer, the old table bin contains
* only a special forwarding node (with hash field "MOVED") that
* contains the next table as its key. On encountering a
* forwarding node, access and update operations restart, using
* the new table.
*
* Each bin transfer requires its bin lock, which can stall
* waiting for locks while resizing. However, because other
* threads can join in and help resize rather than contend for
* locks, average aggregate waits become shorter as resizing
* progresses. The transfer operation must also ensure that all
* accessible bins in both the old and new table are usable by any
* traversal. This is arranged by proceeding from the last bin
* (table.length - 1) up towards the first. Upon seeing a
* forwarding node, traversals (see class Traverser) arrange to
* move to the new table without revisiting nodes. However, to
* ensure that no intervening nodes are skipped, bin splitting can
* only begin after the associated reverse-forwarders are in
* place.
*
* The traversal scheme also applies to partial traversals of
* ranges of bins (via an alternate Traverser constructor)
* to support partitioned aggregate operations. Also, read-only
* operations give up if ever forwarded to a null table, which
* provides support for shutdown-style clearing, which is also not
* currently implemented.
*
* Lazy table initialization minimizes footprint until first use,
* and also avoids resizings when the first operation is from a
* putAll, constructor with map argument, or deserialization.
* These cases attempt to override the initial capacity settings,
* but harmlessly fail to take effect in cases of races.
*
* The element count is maintained using a specialization of
* LongAdder. We need to incorporate a specialization rather than
* just use a LongAdder in order to access implicit
* contention-sensing that leads to creation of multiple
* Cells. The counter mechanics avoid contention on
* updates but can encounter cache thrashing if read too
* frequently during concurrent access. To avoid reading so often,
* resizing under contention is attempted only upon adding to a
* bin already holding two or more nodes. Under uniform hash
* distributions, the probability of this occurring at threshold
* is around 13%, meaning that only about 1 in 8 puts check
* threshold (and after resizing, many fewer do so). The bulk
* putAll operation further reduces contention by only committing
* count updates upon these size checks.
*
* Maintaining API and serialization compatibility with previous
* versions of this class introduces several oddities. Mainly: We
* leave untouched but unused constructor arguments refering to
* concurrencyLevel. We accept a loadFactor constructor argument,
* but apply it only to initial table capacity (which is the only
* time that we can guarantee to honor it.) We also declare an
* unused "Segment" class that is instantiated in minimal form
* only when serializing.
*/
/* ---------------- Constants -------------- */
/**
* The largest possible table capacity. This value must be
* exactly 1<<30 to stay within Java array allocation and indexing
* bounds for power of two table sizes, and is further required
* because the top two bits of 32bit hash fields are used for
* control purposes.
*/
private static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The default initial table capacity. Must be a power of 2
* (i.e., at least 1) and at most MAXIMUM_CAPACITY.
*/
private static final int DEFAULT_CAPACITY = 16;
/**
* The largest possible (non-power of two) array size.
* Needed by toArray and related methods.
*/
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* The default concurrency level for this table. Unused but
* defined for compatibility with previous versions of this class.
*/
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
/**
* The load factor for this table. Overrides of this value in
* constructors affect only the initial table capacity. The
* actual floating point value isn't normally used -- it is
* simpler to use expressions such as {@code n - (n >>> 2)} for
* the associated resizing threshold.
*/
private static final float LOAD_FACTOR = 0.75f;
/**
* The bin count threshold for using a tree rather than list for a
* bin. The value reflects the approximate break-even point for
* using tree-based operations.
*/
private static final int TREE_THRESHOLD = 16;
/**
* Minimum number of rebinnings per transfer step. Ranges are
* subdivided to allow multiple resizer threads. This value
* serves as a lower bound to avoid resizers encountering
* excessive memory contention. The value should be at least
* DEFAULT_CAPACITY.
*/
private static final int MIN_TRANSFER_STRIDE = 16;
/*
* Encodings for Node hash fields. See above for explanation.
*/
static final int MOVED = 0x80000000; // hash field for forwarding nodes
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
/** Number of CPUS, to place bounds on some sizings */
static final int NCPU = Runtime.getRuntime().availableProcessors();
/* ---------------- Counters -------------- */
// Adapted from LongAdder and Striped64.
// See their internal docs for explanation.
// A padded cell for distributing counts
static final class Cell {
volatile long p0, p1, p2, p3, p4, p5, p6;
volatile long value;
volatile long q0, q1, q2, q3, q4, q5, q6;
Cell(long x) { value = x; }
}
/* ---------------- Fields -------------- */
/**
* The array of bins. Lazily initialized upon first insertion.
* Size is always a power of two. Accessed directly by iterators.
*/
transient volatile Node[] table;
/**
* The next table to use; non-null only while resizing.
*/
private transient volatile Node[] nextTable;
/**
* Base counter value, used mainly when there is no contention,
* but also as a fallback during table initialization
* races. Updated via CAS.
*/
private transient volatile long baseCount;
/**
* Table initialization and resizing control. When negative, the
* table is being initialized or resized: -1 for initialization,
* else -(1 + the number of active resizing threads). Otherwise,
* when table is null, holds the initial table size to use upon
* creation, or 0 for default. After initialization, holds the
* next element count value upon which to resize the table.
*/
private transient volatile int sizeCtl;
/**
* The next table index (plus one) to split while resizing.
*/
private transient volatile int transferIndex;
/**
* The least available table index to split while resizing.
*/
private transient volatile int transferOrigin;
/**
* Spinlock (locked via CAS) used when resizing and/or creating Cells.
*/
private transient volatile int cellsBusy;
/**
* Table of counter cells. When non-null, size is a power of 2.
*/
private transient volatile Cell[] counterCells;
// views
private transient KeySetView keySet;
private transient ValuesView values;
private transient EntrySetView entrySet;
/** For serialization compatibility. Null unless serialized; see below */
private Segment[] segments;
/* ---------------- Table element access -------------- */
/*
* Volatile access methods are used for table elements as well as
* elements of in-progress next table while resizing. Uses are
* null checked by callers, and implicitly bounds-checked, relying
* on the invariants that tab arrays have non-zero size, and all
* indices are masked with (tab.length - 1) which is never
* negative and always less than length. Note that, to be correct
* wrt arbitrary concurrency errors by users, bounds checks must
* operate on local variables, which accounts for some odd-looking
* inline assignments below.
*/
@SuppressWarnings("unchecked") static final Node tabAt
(Node[] tab, int i) { // used by Traverser
return (Node)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}
private static final boolean casTabAt
(Node[] tab, int i, Node c, Node v) {
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
private static final void setTabAt
(Node[] tab, int i, Node v) {
U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}
/* ---------------- Nodes -------------- */
/**
* Key-value entry. Note that this is never exported out as a
* user-visible Map.Entry (see MapEntry below). Nodes with a hash
* field of MOVED are special, and do not contain user keys or
* values. Otherwise, keys are never null, and null val fields
* indicate that a node is in the process of being deleted or
* created. For purposes of read-only access, a key may be read
* before a val, but can only be used after checking val to be
* non-null.
*/
static class Node {
final int hash;
final Object key;
volatile V val;
volatile Node next;
Node(int hash, Object key, V val, Node next) {
this.hash = hash;
this.key = key;
this.val = val;
this.next = next;
}
}
/* ---------------- TreeBins -------------- */
/**
* Nodes for use in TreeBins
*/
static final class TreeNode extends Node {
TreeNode parent; // red-black tree links
TreeNode left;
TreeNode right;
TreeNode prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, Object key, V val, Node next, TreeNode parent) {
super(hash, key, val, next);
this.parent = parent;
}
}
/**
* Returns a Class for the given object of the form "class C
* implements Comparable", if one exists, else null. See below
* for explanation.
*/
static Class> comparableClassFor(Object x) {
Class> c, s, cmpc; Type[] ts, as; Type t; ParameterizedType p;
if ((c = x.getClass()) == String.class) // bypass checks
return c;
if ((cmpc = Comparable.class).isAssignableFrom(c)) {
while (cmpc.isAssignableFrom(s = c.getSuperclass()))
c = s; // find topmost comparable class
if ((ts = c.getGenericInterfaces()) != null) {
for (int i = 0; i < ts.length; ++i) {
if (((t = ts[i]) instanceof ParameterizedType) &&
((p = (ParameterizedType)t).getRawType() == cmpc) &&
(as = p.getActualTypeArguments()) != null &&
as.length == 1 && as[0] == c) // type arg is c
return c;
}
}
}
return null;
}
/**
* A specialized form of red-black tree for use in bins
* whose size exceeds a threshold.
*
* TreeBins use a special form of comparison for search and
* related operations (which is the main reason we cannot use
* existing collections such as TreeMaps). TreeBins contain
* Comparable elements, but may contain others, as well as
* elements that are Comparable but not necessarily Comparable
* for the same T, so we cannot invoke compareTo among them. To
* handle this, the tree is ordered primarily by hash value, then
* by Comparable.compareTo order if applicable, else by class
* names if both comparable but not to each other. On lookup at a
* node, if elements are not comparable or compare as 0 then both
* left and right children may need to be searched in the case of
* tied hash values. (This corresponds to the full list search
* that would be necessary if all elements were non-Comparable and
* had tied hashes.) The red-black balancing code is updated from
* pre-jdk-collections
* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
* based in turn on Cormen, Leiserson, and Rivest "Introduction to
* Algorithms" (CLR).
*
* TreeBins also maintain a separate locking discipline than
* regular bins. Because they are forwarded via special MOVED
* nodes at bin heads (which can never change once established),
* we cannot use those nodes as locks. Instead, TreeBin
* extends AbstractQueuedSynchronizer to support a simple form of
* read-write lock. For update operations and table validation,
* the exclusive form of lock behaves in the same way as bin-head
* locks. However, lookups use shared read-lock mechanics to allow
* multiple readers in the absence of writers. Additionally,
* these lookups do not ever block: While the lock is not
* available, they proceed along the slow traversal path (via
* next-pointers) until the lock becomes available or the list is
* exhausted, whichever comes first. (These cases are not fast,
* but maximize aggregate expected throughput.) The AQS mechanics
* for doing this are straightforward. The lock state is held as
* AQS getState(). Read counts are negative; the write count (1)
* is positive. There are no signalling preferences among readers
* and writers. Since we don't need to export full Lock API, we
* just override the minimal AQS methods and use them directly.
*/
static final class TreeBin extends AbstractQueuedSynchronizer {
private static final long serialVersionUID = 2249069246763182397L;
transient TreeNode root; // root of tree
transient TreeNode first; // head of next-pointer list
/* AQS overrides */
public final boolean isHeldExclusively() { return getState() > 0; }
public final boolean tryAcquire(int ignore) {
if (compareAndSetState(0, 1)) {
setExclusiveOwnerThread(Thread.currentThread());
return true;
}
return false;
}
public final boolean tryRelease(int ignore) {
setExclusiveOwnerThread(null);
setState(0);
return true;
}
public final int tryAcquireShared(int ignore) {
for (int c;;) {
if ((c = getState()) > 0)
return -1;
if (compareAndSetState(c, c -1))
return 1;
}
}
public final boolean tryReleaseShared(int ignore) {
int c;
do {} while (!compareAndSetState(c = getState(), c + 1));
return c == -1;
}
/** From CLR */
private void rotateLeft(TreeNode p) {
if (p != null) {
TreeNode r = p.right, pp, rl;
if ((rl = p.right = r.left) != null)
rl.parent = p;
if ((pp = r.parent = p.parent) == null)
root = r;
else if (pp.left == p)
pp.left = r;
else
pp.right = r;
r.left = p;
p.parent = r;
}
}
/** From CLR */
private void rotateRight(TreeNode p) {
if (p != null) {
TreeNode l = p.left, pp, lr;
if ((lr = p.left = l.right) != null)
lr.parent = p;
if ((pp = l.parent = p.parent) == null)
root = l;
else if (pp.right == p)
pp.right = l;
else
pp.left = l;
l.right = p;
p.parent = l;
}
}
/**
* Compares k and x: if k's comparable class (cc) matches x's,
* uses Comparable.compareTo. Otherwise compares on comparable
* class name if both exist, else 0.
*/
@SuppressWarnings("unchecked")
static int cccompare(Class> cc, Object k, Object x) {
Class> cx;
return ((cc != null && (cx = comparableClassFor(x)) != null) ?
((cx == cc) ? ((Comparable