1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/rt/emul/compact/src/main/java/java/util/concurrent/ConcurrentSkipListMap.java Sat Mar 19 10:46:31 2016 +0100
1.3 @@ -0,0 +1,3119 @@
1.4 +/*
1.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.6 + *
1.7 + * This code is free software; you can redistribute it and/or modify it
1.8 + * under the terms of the GNU General Public License version 2 only, as
1.9 + * published by the Free Software Foundation. Oracle designates this
1.10 + * particular file as subject to the "Classpath" exception as provided
1.11 + * by Oracle in the LICENSE file that accompanied this code.
1.12 + *
1.13 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.14 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.15 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.16 + * version 2 for more details (a copy is included in the LICENSE file that
1.17 + * accompanied this code).
1.18 + *
1.19 + * You should have received a copy of the GNU General Public License version
1.20 + * 2 along with this work; if not, write to the Free Software Foundation,
1.21 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.22 + *
1.23 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.24 + * or visit www.oracle.com if you need additional information or have any
1.25 + * questions.
1.26 + */
1.27 +
1.28 +/*
1.29 + * This file is available under and governed by the GNU General Public
1.30 + * License version 2 only, as published by the Free Software Foundation.
1.31 + * However, the following notice accompanied the original version of this
1.32 + * file:
1.33 + *
1.34 + * Written by Doug Lea with assistance from members of JCP JSR-166
1.35 + * Expert Group and released to the public domain, as explained at
1.36 + * http://creativecommons.org/publicdomain/zero/1.0/
1.37 + */
1.38 +
1.39 +package java.util.concurrent;
1.40 +import java.util.*;
1.41 +import java.util.concurrent.atomic.*;
1.42 +
1.43 +/**
1.44 + * A scalable concurrent {@link ConcurrentNavigableMap} implementation.
1.45 + * The map is sorted according to the {@linkplain Comparable natural
1.46 + * ordering} of its keys, or by a {@link Comparator} provided at map
1.47 + * creation time, depending on which constructor is used.
1.48 + *
1.49 + * <p>This class implements a concurrent variant of <a
1.50 + * href="http://en.wikipedia.org/wiki/Skip_list" target="_top">SkipLists</a>
1.51 + * providing expected average <i>log(n)</i> time cost for the
1.52 + * <tt>containsKey</tt>, <tt>get</tt>, <tt>put</tt> and
1.53 + * <tt>remove</tt> operations and their variants. Insertion, removal,
1.54 + * update, and access operations safely execute concurrently by
1.55 + * multiple threads. Iterators are <i>weakly consistent</i>, returning
1.56 + * elements reflecting the state of the map at some point at or since
1.57 + * the creation of the iterator. They do <em>not</em> throw {@link
1.58 + * ConcurrentModificationException}, and may proceed concurrently with
1.59 + * other operations. Ascending key ordered views and their iterators
1.60 + * are faster than descending ones.
1.61 + *
1.62 + * <p>All <tt>Map.Entry</tt> pairs returned by methods in this class
1.63 + * and its views represent snapshots of mappings at the time they were
1.64 + * produced. They do <em>not</em> support the <tt>Entry.setValue</tt>
1.65 + * method. (Note however that it is possible to change mappings in the
1.66 + * associated map using <tt>put</tt>, <tt>putIfAbsent</tt>, or
1.67 + * <tt>replace</tt>, depending on exactly which effect you need.)
1.68 + *
1.69 + * <p>Beware that, unlike in most collections, the <tt>size</tt>
1.70 + * method is <em>not</em> a constant-time operation. Because of the
1.71 + * asynchronous nature of these maps, determining the current number
1.72 + * of elements requires a traversal of the elements, and so may report
1.73 + * inaccurate results if this collection is modified during traversal.
1.74 + * Additionally, the bulk operations <tt>putAll</tt>, <tt>equals</tt>,
1.75 + * <tt>toArray</tt>, <tt>containsValue</tt>, and <tt>clear</tt> are
1.76 + * <em>not</em> guaranteed to be performed atomically. For example, an
1.77 + * iterator operating concurrently with a <tt>putAll</tt> operation
1.78 + * might view only some of the added elements.
1.79 + *
1.80 + * <p>This class and its views and iterators implement all of the
1.81 + * <em>optional</em> methods of the {@link Map} and {@link Iterator}
1.82 + * interfaces. Like most other concurrent collections, this class does
1.83 + * <em>not</em> permit the use of <tt>null</tt> keys or values because some
1.84 + * null return values cannot be reliably distinguished from the absence of
1.85 + * elements.
1.86 + *
1.87 + * <p>This class is a member of the
1.88 + * <a href="{@docRoot}/../technotes/guides/collections/index.html">
1.89 + * Java Collections Framework</a>.
1.90 + *
1.91 + * @author Doug Lea
1.92 + * @param <K> the type of keys maintained by this map
1.93 + * @param <V> the type of mapped values
1.94 + * @since 1.6
1.95 + */
1.96 +public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
1.97 + implements ConcurrentNavigableMap<K,V>,
1.98 + Cloneable,
1.99 + java.io.Serializable {
1.100 + /*
1.101 + * This class implements a tree-like two-dimensionally linked skip
1.102 + * list in which the index levels are represented in separate
1.103 + * nodes from the base nodes holding data. There are two reasons
1.104 + * for taking this approach instead of the usual array-based
1.105 + * structure: 1) Array based implementations seem to encounter
1.106 + * more complexity and overhead 2) We can use cheaper algorithms
1.107 + * for the heavily-traversed index lists than can be used for the
1.108 + * base lists. Here's a picture of some of the basics for a
1.109 + * possible list with 2 levels of index:
1.110 + *
1.111 + * Head nodes Index nodes
1.112 + * +-+ right +-+ +-+
1.113 + * |2|---------------->| |--------------------->| |->null
1.114 + * +-+ +-+ +-+
1.115 + * | down | |
1.116 + * v v v
1.117 + * +-+ +-+ +-+ +-+ +-+ +-+
1.118 + * |1|----------->| |->| |------>| |----------->| |------>| |->null
1.119 + * +-+ +-+ +-+ +-+ +-+ +-+
1.120 + * v | | | | |
1.121 + * Nodes next v v v v v
1.122 + * +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
1.123 + * | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null
1.124 + * +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
1.125 + *
1.126 + * The base lists use a variant of the HM linked ordered set
1.127 + * algorithm. See Tim Harris, "A pragmatic implementation of
1.128 + * non-blocking linked lists"
1.129 + * http://www.cl.cam.ac.uk/~tlh20/publications.html and Maged
1.130 + * Michael "High Performance Dynamic Lock-Free Hash Tables and
1.131 + * List-Based Sets"
1.132 + * http://www.research.ibm.com/people/m/michael/pubs.htm. The
1.133 + * basic idea in these lists is to mark the "next" pointers of
1.134 + * deleted nodes when deleting to avoid conflicts with concurrent
1.135 + * insertions, and when traversing to keep track of triples
1.136 + * (predecessor, node, successor) in order to detect when and how
1.137 + * to unlink these deleted nodes.
1.138 + *
1.139 + * Rather than using mark-bits to mark list deletions (which can
1.140 + * be slow and space-intensive using AtomicMarkedReference), nodes
1.141 + * use direct CAS'able next pointers. On deletion, instead of
1.142 + * marking a pointer, they splice in another node that can be
1.143 + * thought of as standing for a marked pointer (indicating this by
1.144 + * using otherwise impossible field values). Using plain nodes
1.145 + * acts roughly like "boxed" implementations of marked pointers,
1.146 + * but uses new nodes only when nodes are deleted, not for every
1.147 + * link. This requires less space and supports faster
1.148 + * traversal. Even if marked references were better supported by
1.149 + * JVMs, traversal using this technique might still be faster
1.150 + * because any search need only read ahead one more node than
1.151 + * otherwise required (to check for trailing marker) rather than
1.152 + * unmasking mark bits or whatever on each read.
1.153 + *
1.154 + * This approach maintains the essential property needed in the HM
1.155 + * algorithm of changing the next-pointer of a deleted node so
1.156 + * that any other CAS of it will fail, but implements the idea by
1.157 + * changing the pointer to point to a different node, not by
1.158 + * marking it. While it would be possible to further squeeze
1.159 + * space by defining marker nodes not to have key/value fields, it
1.160 + * isn't worth the extra type-testing overhead. The deletion
1.161 + * markers are rarely encountered during traversal and are
1.162 + * normally quickly garbage collected. (Note that this technique
1.163 + * would not work well in systems without garbage collection.)
1.164 + *
1.165 + * In addition to using deletion markers, the lists also use
1.166 + * nullness of value fields to indicate deletion, in a style
1.167 + * similar to typical lazy-deletion schemes. If a node's value is
1.168 + * null, then it is considered logically deleted and ignored even
1.169 + * though it is still reachable. This maintains proper control of
1.170 + * concurrent replace vs delete operations -- an attempted replace
1.171 + * must fail if a delete beat it by nulling field, and a delete
1.172 + * must return the last non-null value held in the field. (Note:
1.173 + * Null, rather than some special marker, is used for value fields
1.174 + * here because it just so happens to mesh with the Map API
1.175 + * requirement that method get returns null if there is no
1.176 + * mapping, which allows nodes to remain concurrently readable
1.177 + * even when deleted. Using any other marker value here would be
1.178 + * messy at best.)
1.179 + *
1.180 + * Here's the sequence of events for a deletion of node n with
1.181 + * predecessor b and successor f, initially:
1.182 + *
1.183 + * +------+ +------+ +------+
1.184 + * ... | b |------>| n |----->| f | ...
1.185 + * +------+ +------+ +------+
1.186 + *
1.187 + * 1. CAS n's value field from non-null to null.
1.188 + * From this point on, no public operations encountering
1.189 + * the node consider this mapping to exist. However, other
1.190 + * ongoing insertions and deletions might still modify
1.191 + * n's next pointer.
1.192 + *
1.193 + * 2. CAS n's next pointer to point to a new marker node.
1.194 + * From this point on, no other nodes can be appended to n.
1.195 + * which avoids deletion errors in CAS-based linked lists.
1.196 + *
1.197 + * +------+ +------+ +------+ +------+
1.198 + * ... | b |------>| n |----->|marker|------>| f | ...
1.199 + * +------+ +------+ +------+ +------+
1.200 + *
1.201 + * 3. CAS b's next pointer over both n and its marker.
1.202 + * From this point on, no new traversals will encounter n,
1.203 + * and it can eventually be GCed.
1.204 + * +------+ +------+
1.205 + * ... | b |----------------------------------->| f | ...
1.206 + * +------+ +------+
1.207 + *
1.208 + * A failure at step 1 leads to simple retry due to a lost race
1.209 + * with another operation. Steps 2-3 can fail because some other
1.210 + * thread noticed during a traversal a node with null value and
1.211 + * helped out by marking and/or unlinking. This helping-out
1.212 + * ensures that no thread can become stuck waiting for progress of
1.213 + * the deleting thread. The use of marker nodes slightly
1.214 + * complicates helping-out code because traversals must track
1.215 + * consistent reads of up to four nodes (b, n, marker, f), not
1.216 + * just (b, n, f), although the next field of a marker is
1.217 + * immutable, and once a next field is CAS'ed to point to a
1.218 + * marker, it never again changes, so this requires less care.
1.219 + *
1.220 + * Skip lists add indexing to this scheme, so that the base-level
1.221 + * traversals start close to the locations being found, inserted
1.222 + * or deleted -- usually base level traversals only traverse a few
1.223 + * nodes. This doesn't change the basic algorithm except for the
1.224 + * need to make sure base traversals start at predecessors (here,
1.225 + * b) that are not (structurally) deleted, otherwise retrying
1.226 + * after processing the deletion.
1.227 + *
1.228 + * Index levels are maintained as lists with volatile next fields,
1.229 + * using CAS to link and unlink. Races are allowed in index-list
1.230 + * operations that can (rarely) fail to link in a new index node
1.231 + * or delete one. (We can't do this of course for data nodes.)
1.232 + * However, even when this happens, the index lists remain sorted,
1.233 + * so correctly serve as indices. This can impact performance,
1.234 + * but since skip lists are probabilistic anyway, the net result
1.235 + * is that under contention, the effective "p" value may be lower
1.236 + * than its nominal value. And race windows are kept small enough
1.237 + * that in practice these failures are rare, even under a lot of
1.238 + * contention.
1.239 + *
1.240 + * The fact that retries (for both base and index lists) are
1.241 + * relatively cheap due to indexing allows some minor
1.242 + * simplifications of retry logic. Traversal restarts are
1.243 + * performed after most "helping-out" CASes. This isn't always
1.244 + * strictly necessary, but the implicit backoffs tend to help
1.245 + * reduce other downstream failed CAS's enough to outweigh restart
1.246 + * cost. This worsens the worst case, but seems to improve even
1.247 + * highly contended cases.
1.248 + *
1.249 + * Unlike most skip-list implementations, index insertion and
1.250 + * deletion here require a separate traversal pass occuring after
1.251 + * the base-level action, to add or remove index nodes. This adds
1.252 + * to single-threaded overhead, but improves contended
1.253 + * multithreaded performance by narrowing interference windows,
1.254 + * and allows deletion to ensure that all index nodes will be made
1.255 + * unreachable upon return from a public remove operation, thus
1.256 + * avoiding unwanted garbage retention. This is more important
1.257 + * here than in some other data structures because we cannot null
1.258 + * out node fields referencing user keys since they might still be
1.259 + * read by other ongoing traversals.
1.260 + *
1.261 + * Indexing uses skip list parameters that maintain good search
1.262 + * performance while using sparser-than-usual indices: The
1.263 + * hardwired parameters k=1, p=0.5 (see method randomLevel) mean
1.264 + * that about one-quarter of the nodes have indices. Of those that
1.265 + * do, half have one level, a quarter have two, and so on (see
1.266 + * Pugh's Skip List Cookbook, sec 3.4). The expected total space
1.267 + * requirement for a map is slightly less than for the current
1.268 + * implementation of java.util.TreeMap.
1.269 + *
1.270 + * Changing the level of the index (i.e, the height of the
1.271 + * tree-like structure) also uses CAS. The head index has initial
1.272 + * level/height of one. Creation of an index with height greater
1.273 + * than the current level adds a level to the head index by
1.274 + * CAS'ing on a new top-most head. To maintain good performance
1.275 + * after a lot of removals, deletion methods heuristically try to
1.276 + * reduce the height if the topmost levels appear to be empty.
1.277 + * This may encounter races in which it possible (but rare) to
1.278 + * reduce and "lose" a level just as it is about to contain an
1.279 + * index (that will then never be encountered). This does no
1.280 + * structural harm, and in practice appears to be a better option
1.281 + * than allowing unrestrained growth of levels.
1.282 + *
1.283 + * The code for all this is more verbose than you'd like. Most
1.284 + * operations entail locating an element (or position to insert an
1.285 + * element). The code to do this can't be nicely factored out
1.286 + * because subsequent uses require a snapshot of predecessor
1.287 + * and/or successor and/or value fields which can't be returned
1.288 + * all at once, at least not without creating yet another object
1.289 + * to hold them -- creating such little objects is an especially
1.290 + * bad idea for basic internal search operations because it adds
1.291 + * to GC overhead. (This is one of the few times I've wished Java
1.292 + * had macros.) Instead, some traversal code is interleaved within
1.293 + * insertion and removal operations. The control logic to handle
1.294 + * all the retry conditions is sometimes twisty. Most search is
1.295 + * broken into 2 parts. findPredecessor() searches index nodes
1.296 + * only, returning a base-level predecessor of the key. findNode()
1.297 + * finishes out the base-level search. Even with this factoring,
1.298 + * there is a fair amount of near-duplication of code to handle
1.299 + * variants.
1.300 + *
1.301 + * For explanation of algorithms sharing at least a couple of
1.302 + * features with this one, see Mikhail Fomitchev's thesis
1.303 + * (http://www.cs.yorku.ca/~mikhail/), Keir Fraser's thesis
1.304 + * (http://www.cl.cam.ac.uk/users/kaf24/), and Hakan Sundell's
1.305 + * thesis (http://www.cs.chalmers.se/~phs/).
1.306 + *
1.307 + * Given the use of tree-like index nodes, you might wonder why
1.308 + * this doesn't use some kind of search tree instead, which would
1.309 + * support somewhat faster search operations. The reason is that
1.310 + * there are no known efficient lock-free insertion and deletion
1.311 + * algorithms for search trees. The immutability of the "down"
1.312 + * links of index nodes (as opposed to mutable "left" fields in
1.313 + * true trees) makes this tractable using only CAS operations.
1.314 + *
1.315 + * Notation guide for local variables
1.316 + * Node: b, n, f for predecessor, node, successor
1.317 + * Index: q, r, d for index node, right, down.
1.318 + * t for another index node
1.319 + * Head: h
1.320 + * Levels: j
1.321 + * Keys: k, key
1.322 + * Values: v, value
1.323 + * Comparisons: c
1.324 + */
1.325 +
1.326 + private static final long serialVersionUID = -8627078645895051609L;
1.327 +
1.328 + /**
1.329 + * Generates the initial random seed for the cheaper per-instance
1.330 + * random number generators used in randomLevel.
1.331 + */
1.332 + private static final Random seedGenerator = new Random();
1.333 +
1.334 + /**
1.335 + * Special value used to identify base-level header
1.336 + */
1.337 + private static final Object BASE_HEADER = new Object();
1.338 +
1.339 + /**
1.340 + * The topmost head index of the skiplist.
1.341 + */
1.342 + private transient volatile HeadIndex<K,V> head;
1.343 +
1.344 + /**
1.345 + * The comparator used to maintain order in this map, or null
1.346 + * if using natural ordering.
1.347 + * @serial
1.348 + */
1.349 + private final Comparator<? super K> comparator;
1.350 +
1.351 + /**
1.352 + * Seed for simple random number generator. Not volatile since it
1.353 + * doesn't matter too much if different threads don't see updates.
1.354 + */
1.355 + private transient int randomSeed;
1.356 +
1.357 + /** Lazily initialized key set */
1.358 + private transient KeySet keySet;
1.359 + /** Lazily initialized entry set */
1.360 + private transient EntrySet entrySet;
1.361 + /** Lazily initialized values collection */
1.362 + private transient Values values;
1.363 + /** Lazily initialized descending key set */
1.364 + private transient ConcurrentNavigableMap<K,V> descendingMap;
1.365 +
1.366 + /**
1.367 + * Initializes or resets state. Needed by constructors, clone,
1.368 + * clear, readObject. and ConcurrentSkipListSet.clone.
1.369 + * (Note that comparator must be separately initialized.)
1.370 + */
1.371 + final void initialize() {
1.372 + keySet = null;
1.373 + entrySet = null;
1.374 + values = null;
1.375 + descendingMap = null;
1.376 + randomSeed = seedGenerator.nextInt() | 0x0100; // ensure nonzero
1.377 + head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),
1.378 + null, null, 1);
1.379 + }
1.380 +
1.381 + /**
1.382 + * compareAndSet head node
1.383 + */
1.384 + private boolean casHead(HeadIndex<K,V> cmp, HeadIndex<K,V> val) {
1.385 + return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val);
1.386 + }
1.387 +
1.388 + /* ---------------- Nodes -------------- */
1.389 +
1.390 + /**
1.391 + * Nodes hold keys and values, and are singly linked in sorted
1.392 + * order, possibly with some intervening marker nodes. The list is
1.393 + * headed by a dummy node accessible as head.node. The value field
1.394 + * is declared only as Object because it takes special non-V
1.395 + * values for marker and header nodes.
1.396 + */
1.397 + static final class Node<K,V> {
1.398 + final K key;
1.399 + volatile Object value;
1.400 + volatile Node<K,V> next;
1.401 +
1.402 + /**
1.403 + * Creates a new regular node.
1.404 + */
1.405 + Node(K key, Object value, Node<K,V> next) {
1.406 + this.key = key;
1.407 + this.value = value;
1.408 + this.next = next;
1.409 + }
1.410 +
1.411 + /**
1.412 + * Creates a new marker node. A marker is distinguished by
1.413 + * having its value field point to itself. Marker nodes also
1.414 + * have null keys, a fact that is exploited in a few places,
1.415 + * but this doesn't distinguish markers from the base-level
1.416 + * header node (head.node), which also has a null key.
1.417 + */
1.418 + Node(Node<K,V> next) {
1.419 + this.key = null;
1.420 + this.value = this;
1.421 + this.next = next;
1.422 + }
1.423 +
1.424 + /**
1.425 + * compareAndSet value field
1.426 + */
1.427 + boolean casValue(Object cmp, Object val) {
1.428 + return UNSAFE.compareAndSwapObject(this, valueOffset, cmp, val);
1.429 + }
1.430 +
1.431 + /**
1.432 + * compareAndSet next field
1.433 + */
1.434 + boolean casNext(Node<K,V> cmp, Node<K,V> val) {
1.435 + return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
1.436 + }
1.437 +
1.438 + /**
1.439 + * Returns true if this node is a marker. This method isn't
1.440 + * actually called in any current code checking for markers
1.441 + * because callers will have already read value field and need
1.442 + * to use that read (not another done here) and so directly
1.443 + * test if value points to node.
1.444 + * @param n a possibly null reference to a node
1.445 + * @return true if this node is a marker node
1.446 + */
1.447 + boolean isMarker() {
1.448 + return value == this;
1.449 + }
1.450 +
1.451 + /**
1.452 + * Returns true if this node is the header of base-level list.
1.453 + * @return true if this node is header node
1.454 + */
1.455 + boolean isBaseHeader() {
1.456 + return value == BASE_HEADER;
1.457 + }
1.458 +
1.459 + /**
1.460 + * Tries to append a deletion marker to this node.
1.461 + * @param f the assumed current successor of this node
1.462 + * @return true if successful
1.463 + */
1.464 + boolean appendMarker(Node<K,V> f) {
1.465 + return casNext(f, new Node<K,V>(f));
1.466 + }
1.467 +
1.468 + /**
1.469 + * Helps out a deletion by appending marker or unlinking from
1.470 + * predecessor. This is called during traversals when value
1.471 + * field seen to be null.
1.472 + * @param b predecessor
1.473 + * @param f successor
1.474 + */
1.475 + void helpDelete(Node<K,V> b, Node<K,V> f) {
1.476 + /*
1.477 + * Rechecking links and then doing only one of the
1.478 + * help-out stages per call tends to minimize CAS
1.479 + * interference among helping threads.
1.480 + */
1.481 + if (f == next && this == b.next) {
1.482 + if (f == null || f.value != f) // not already marked
1.483 + appendMarker(f);
1.484 + else
1.485 + b.casNext(this, f.next);
1.486 + }
1.487 + }
1.488 +
1.489 + /**
1.490 + * Returns value if this node contains a valid key-value pair,
1.491 + * else null.
1.492 + * @return this node's value if it isn't a marker or header or
1.493 + * is deleted, else null.
1.494 + */
1.495 + V getValidValue() {
1.496 + Object v = value;
1.497 + if (v == this || v == BASE_HEADER)
1.498 + return null;
1.499 + return (V)v;
1.500 + }
1.501 +
1.502 + /**
1.503 + * Creates and returns a new SimpleImmutableEntry holding current
1.504 + * mapping if this node holds a valid value, else null.
1.505 + * @return new entry or null
1.506 + */
1.507 + AbstractMap.SimpleImmutableEntry<K,V> createSnapshot() {
1.508 + V v = getValidValue();
1.509 + if (v == null)
1.510 + return null;
1.511 + return new AbstractMap.SimpleImmutableEntry<K,V>(key, v);
1.512 + }
1.513 +
1.514 + // UNSAFE mechanics
1.515 +
1.516 + private static final sun.misc.Unsafe UNSAFE;
1.517 + private static final long valueOffset;
1.518 + private static final long nextOffset;
1.519 +
1.520 + static {
1.521 + try {
1.522 + UNSAFE = sun.misc.Unsafe.getUnsafe();
1.523 + Class k = Node.class;
1.524 + valueOffset = UNSAFE.objectFieldOffset
1.525 + (k.getDeclaredField("value"));
1.526 + nextOffset = UNSAFE.objectFieldOffset
1.527 + (k.getDeclaredField("next"));
1.528 + } catch (Exception e) {
1.529 + throw new Error(e);
1.530 + }
1.531 + }
1.532 + }
1.533 +
1.534 + /* ---------------- Indexing -------------- */
1.535 +
1.536 + /**
1.537 + * Index nodes represent the levels of the skip list. Note that
1.538 + * even though both Nodes and Indexes have forward-pointing
1.539 + * fields, they have different types and are handled in different
1.540 + * ways, that can't nicely be captured by placing field in a
1.541 + * shared abstract class.
1.542 + */
1.543 + static class Index<K,V> {
1.544 + final Node<K,V> node;
1.545 + final Index<K,V> down;
1.546 + volatile Index<K,V> right;
1.547 +
1.548 + /**
1.549 + * Creates index node with given values.
1.550 + */
1.551 + Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
1.552 + this.node = node;
1.553 + this.down = down;
1.554 + this.right = right;
1.555 + }
1.556 +
1.557 + /**
1.558 + * compareAndSet right field
1.559 + */
1.560 + final boolean casRight(Index<K,V> cmp, Index<K,V> val) {
1.561 + return UNSAFE.compareAndSwapObject(this, rightOffset, cmp, val);
1.562 + }
1.563 +
1.564 + /**
1.565 + * Returns true if the node this indexes has been deleted.
1.566 + * @return true if indexed node is known to be deleted
1.567 + */
1.568 + final boolean indexesDeletedNode() {
1.569 + return node.value == null;
1.570 + }
1.571 +
1.572 + /**
1.573 + * Tries to CAS newSucc as successor. To minimize races with
1.574 + * unlink that may lose this index node, if the node being
1.575 + * indexed is known to be deleted, it doesn't try to link in.
1.576 + * @param succ the expected current successor
1.577 + * @param newSucc the new successor
1.578 + * @return true if successful
1.579 + */
1.580 + final boolean link(Index<K,V> succ, Index<K,V> newSucc) {
1.581 + Node<K,V> n = node;
1.582 + newSucc.right = succ;
1.583 + return n.value != null && casRight(succ, newSucc);
1.584 + }
1.585 +
1.586 + /**
1.587 + * Tries to CAS right field to skip over apparent successor
1.588 + * succ. Fails (forcing a retraversal by caller) if this node
1.589 + * is known to be deleted.
1.590 + * @param succ the expected current successor
1.591 + * @return true if successful
1.592 + */
1.593 + final boolean unlink(Index<K,V> succ) {
1.594 + return !indexesDeletedNode() && casRight(succ, succ.right);
1.595 + }
1.596 +
1.597 + // Unsafe mechanics
1.598 + private static final sun.misc.Unsafe UNSAFE;
1.599 + private static final long rightOffset;
1.600 + static {
1.601 + try {
1.602 + UNSAFE = sun.misc.Unsafe.getUnsafe();
1.603 + Class k = Index.class;
1.604 + rightOffset = UNSAFE.objectFieldOffset
1.605 + (k.getDeclaredField("right"));
1.606 + } catch (Exception e) {
1.607 + throw new Error(e);
1.608 + }
1.609 + }
1.610 + }
1.611 +
1.612 + /* ---------------- Head nodes -------------- */
1.613 +
1.614 + /**
1.615 + * Nodes heading each level keep track of their level.
1.616 + */
1.617 + static final class HeadIndex<K,V> extends Index<K,V> {
1.618 + final int level;
1.619 + HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {
1.620 + super(node, down, right);
1.621 + this.level = level;
1.622 + }
1.623 + }
1.624 +
1.625 + /* ---------------- Comparison utilities -------------- */
1.626 +
1.627 + /**
1.628 + * Represents a key with a comparator as a Comparable.
1.629 + *
1.630 + * Because most sorted collections seem to use natural ordering on
1.631 + * Comparables (Strings, Integers, etc), most internal methods are
1.632 + * geared to use them. This is generally faster than checking
1.633 + * per-comparison whether to use comparator or comparable because
1.634 + * it doesn't require a (Comparable) cast for each comparison.
1.635 + * (Optimizers can only sometimes remove such redundant checks
1.636 + * themselves.) When Comparators are used,
1.637 + * ComparableUsingComparators are created so that they act in the
1.638 + * same way as natural orderings. This penalizes use of
1.639 + * Comparators vs Comparables, which seems like the right
1.640 + * tradeoff.
1.641 + */
1.642 + static final class ComparableUsingComparator<K> implements Comparable<K> {
1.643 + final K actualKey;
1.644 + final Comparator<? super K> cmp;
1.645 + ComparableUsingComparator(K key, Comparator<? super K> cmp) {
1.646 + this.actualKey = key;
1.647 + this.cmp = cmp;
1.648 + }
1.649 + public int compareTo(K k2) {
1.650 + return cmp.compare(actualKey, k2);
1.651 + }
1.652 + }
1.653 +
1.654 + /**
1.655 + * If using comparator, return a ComparableUsingComparator, else
1.656 + * cast key as Comparable, which may cause ClassCastException,
1.657 + * which is propagated back to caller.
1.658 + */
1.659 + private Comparable<? super K> comparable(Object key)
1.660 + throws ClassCastException {
1.661 + if (key == null)
1.662 + throw new NullPointerException();
1.663 + if (comparator != null)
1.664 + return new ComparableUsingComparator<K>((K)key, comparator);
1.665 + else
1.666 + return (Comparable<? super K>)key;
1.667 + }
1.668 +
1.669 + /**
1.670 + * Compares using comparator or natural ordering. Used when the
1.671 + * ComparableUsingComparator approach doesn't apply.
1.672 + */
1.673 + int compare(K k1, K k2) throws ClassCastException {
1.674 + Comparator<? super K> cmp = comparator;
1.675 + if (cmp != null)
1.676 + return cmp.compare(k1, k2);
1.677 + else
1.678 + return ((Comparable<? super K>)k1).compareTo(k2);
1.679 + }
1.680 +
1.681 + /**
1.682 + * Returns true if given key greater than or equal to least and
1.683 + * strictly less than fence, bypassing either test if least or
1.684 + * fence are null. Needed mainly in submap operations.
1.685 + */
1.686 + boolean inHalfOpenRange(K key, K least, K fence) {
1.687 + if (key == null)
1.688 + throw new NullPointerException();
1.689 + return ((least == null || compare(key, least) >= 0) &&
1.690 + (fence == null || compare(key, fence) < 0));
1.691 + }
1.692 +
1.693 + /**
1.694 + * Returns true if given key greater than or equal to least and less
1.695 + * or equal to fence. Needed mainly in submap operations.
1.696 + */
1.697 + boolean inOpenRange(K key, K least, K fence) {
1.698 + if (key == null)
1.699 + throw new NullPointerException();
1.700 + return ((least == null || compare(key, least) >= 0) &&
1.701 + (fence == null || compare(key, fence) <= 0));
1.702 + }
1.703 +
1.704 + /* ---------------- Traversal -------------- */
1.705 +
1.706 + /**
1.707 + * Returns a base-level node with key strictly less than given key,
1.708 + * or the base-level header if there is no such node. Also
1.709 + * unlinks indexes to deleted nodes found along the way. Callers
1.710 + * rely on this side-effect of clearing indices to deleted nodes.
1.711 + * @param key the key
1.712 + * @return a predecessor of key
1.713 + */
1.714 + private Node<K,V> findPredecessor(Comparable<? super K> key) {
1.715 + if (key == null)
1.716 + throw new NullPointerException(); // don't postpone errors
1.717 + for (;;) {
1.718 + Index<K,V> q = head;
1.719 + Index<K,V> r = q.right;
1.720 + for (;;) {
1.721 + if (r != null) {
1.722 + Node<K,V> n = r.node;
1.723 + K k = n.key;
1.724 + if (n.value == null) {
1.725 + if (!q.unlink(r))
1.726 + break; // restart
1.727 + r = q.right; // reread r
1.728 + continue;
1.729 + }
1.730 + if (key.compareTo(k) > 0) {
1.731 + q = r;
1.732 + r = r.right;
1.733 + continue;
1.734 + }
1.735 + }
1.736 + Index<K,V> d = q.down;
1.737 + if (d != null) {
1.738 + q = d;
1.739 + r = d.right;
1.740 + } else
1.741 + return q.node;
1.742 + }
1.743 + }
1.744 + }
1.745 +
1.746 + /**
1.747 + * Returns node holding key or null if no such, clearing out any
1.748 + * deleted nodes seen along the way. Repeatedly traverses at
1.749 + * base-level looking for key starting at predecessor returned
1.750 + * from findPredecessor, processing base-level deletions as
1.751 + * encountered. Some callers rely on this side-effect of clearing
1.752 + * deleted nodes.
1.753 + *
1.754 + * Restarts occur, at traversal step centered on node n, if:
1.755 + *
1.756 + * (1) After reading n's next field, n is no longer assumed
1.757 + * predecessor b's current successor, which means that
1.758 + * we don't have a consistent 3-node snapshot and so cannot
1.759 + * unlink any subsequent deleted nodes encountered.
1.760 + *
1.761 + * (2) n's value field is null, indicating n is deleted, in
1.762 + * which case we help out an ongoing structural deletion
1.763 + * before retrying. Even though there are cases where such
1.764 + * unlinking doesn't require restart, they aren't sorted out
1.765 + * here because doing so would not usually outweigh cost of
1.766 + * restarting.
1.767 + *
1.768 + * (3) n is a marker or n's predecessor's value field is null,
1.769 + * indicating (among other possibilities) that
1.770 + * findPredecessor returned a deleted node. We can't unlink
1.771 + * the node because we don't know its predecessor, so rely
1.772 + * on another call to findPredecessor to notice and return
1.773 + * some earlier predecessor, which it will do. This check is
1.774 + * only strictly needed at beginning of loop, (and the
1.775 + * b.value check isn't strictly needed at all) but is done
1.776 + * each iteration to help avoid contention with other
1.777 + * threads by callers that will fail to be able to change
1.778 + * links, and so will retry anyway.
1.779 + *
1.780 + * The traversal loops in doPut, doRemove, and findNear all
1.781 + * include the same three kinds of checks. And specialized
1.782 + * versions appear in findFirst, and findLast and their
1.783 + * variants. They can't easily share code because each uses the
1.784 + * reads of fields held in locals occurring in the orders they
1.785 + * were performed.
1.786 + *
1.787 + * @param key the key
1.788 + * @return node holding key, or null if no such
1.789 + */
1.790 + private Node<K,V> findNode(Comparable<? super K> key) {
1.791 + for (;;) {
1.792 + Node<K,V> b = findPredecessor(key);
1.793 + Node<K,V> n = b.next;
1.794 + for (;;) {
1.795 + if (n == null)
1.796 + return null;
1.797 + Node<K,V> f = n.next;
1.798 + if (n != b.next) // inconsistent read
1.799 + break;
1.800 + Object v = n.value;
1.801 + if (v == null) { // n is deleted
1.802 + n.helpDelete(b, f);
1.803 + break;
1.804 + }
1.805 + if (v == n || b.value == null) // b is deleted
1.806 + break;
1.807 + int c = key.compareTo(n.key);
1.808 + if (c == 0)
1.809 + return n;
1.810 + if (c < 0)
1.811 + return null;
1.812 + b = n;
1.813 + n = f;
1.814 + }
1.815 + }
1.816 + }
1.817 +
1.818 + /**
1.819 + * Gets value for key using findNode.
1.820 + * @param okey the key
1.821 + * @return the value, or null if absent
1.822 + */
1.823 + private V doGet(Object okey) {
1.824 + Comparable<? super K> key = comparable(okey);
1.825 + /*
1.826 + * Loop needed here and elsewhere in case value field goes
1.827 + * null just as it is about to be returned, in which case we
1.828 + * lost a race with a deletion, so must retry.
1.829 + */
1.830 + for (;;) {
1.831 + Node<K,V> n = findNode(key);
1.832 + if (n == null)
1.833 + return null;
1.834 + Object v = n.value;
1.835 + if (v != null)
1.836 + return (V)v;
1.837 + }
1.838 + }
1.839 +
1.840 + /* ---------------- Insertion -------------- */
1.841 +
1.842 + /**
1.843 + * Main insertion method. Adds element if not present, or
1.844 + * replaces value if present and onlyIfAbsent is false.
1.845 + * @param kkey the key
1.846 + * @param value the value that must be associated with key
1.847 + * @param onlyIfAbsent if should not insert if already present
1.848 + * @return the old value, or null if newly inserted
1.849 + */
1.850 + private V doPut(K kkey, V value, boolean onlyIfAbsent) {
1.851 + Comparable<? super K> key = comparable(kkey);
1.852 + for (;;) {
1.853 + Node<K,V> b = findPredecessor(key);
1.854 + Node<K,V> n = b.next;
1.855 + for (;;) {
1.856 + if (n != null) {
1.857 + Node<K,V> f = n.next;
1.858 + if (n != b.next) // inconsistent read
1.859 + break;
1.860 + Object v = n.value;
1.861 + if (v == null) { // n is deleted
1.862 + n.helpDelete(b, f);
1.863 + break;
1.864 + }
1.865 + if (v == n || b.value == null) // b is deleted
1.866 + break;
1.867 + int c = key.compareTo(n.key);
1.868 + if (c > 0) {
1.869 + b = n;
1.870 + n = f;
1.871 + continue;
1.872 + }
1.873 + if (c == 0) {
1.874 + if (onlyIfAbsent || n.casValue(v, value))
1.875 + return (V)v;
1.876 + else
1.877 + break; // restart if lost race to replace value
1.878 + }
1.879 + // else c < 0; fall through
1.880 + }
1.881 +
1.882 + Node<K,V> z = new Node<K,V>(kkey, value, n);
1.883 + if (!b.casNext(n, z))
1.884 + break; // restart if lost race to append to b
1.885 + int level = randomLevel();
1.886 + if (level > 0)
1.887 + insertIndex(z, level);
1.888 + return null;
1.889 + }
1.890 + }
1.891 + }
1.892 +
1.893 + /**
1.894 + * Returns a random level for inserting a new node.
1.895 + * Hardwired to k=1, p=0.5, max 31 (see above and
1.896 + * Pugh's "Skip List Cookbook", sec 3.4).
1.897 + *
1.898 + * This uses the simplest of the generators described in George
1.899 + * Marsaglia's "Xorshift RNGs" paper. This is not a high-quality
1.900 + * generator but is acceptable here.
1.901 + */
1.902 + private int randomLevel() {
1.903 + int x = randomSeed;
1.904 + x ^= x << 13;
1.905 + x ^= x >>> 17;
1.906 + randomSeed = x ^= x << 5;
1.907 + if ((x & 0x80000001) != 0) // test highest and lowest bits
1.908 + return 0;
1.909 + int level = 1;
1.910 + while (((x >>>= 1) & 1) != 0) ++level;
1.911 + return level;
1.912 + }
1.913 +
1.914 + /**
1.915 + * Creates and adds index nodes for the given node.
1.916 + * @param z the node
1.917 + * @param level the level of the index
1.918 + */
1.919 + private void insertIndex(Node<K,V> z, int level) {
1.920 + HeadIndex<K,V> h = head;
1.921 + int max = h.level;
1.922 +
1.923 + if (level <= max) {
1.924 + Index<K,V> idx = null;
1.925 + for (int i = 1; i <= level; ++i)
1.926 + idx = new Index<K,V>(z, idx, null);
1.927 + addIndex(idx, h, level);
1.928 +
1.929 + } else { // Add a new level
1.930 + /*
1.931 + * To reduce interference by other threads checking for
1.932 + * empty levels in tryReduceLevel, new levels are added
1.933 + * with initialized right pointers. Which in turn requires
1.934 + * keeping levels in an array to access them while
1.935 + * creating new head index nodes from the opposite
1.936 + * direction.
1.937 + */
1.938 + level = max + 1;
1.939 + Index<K,V>[] idxs = (Index<K,V>[])new Index[level+1];
1.940 + Index<K,V> idx = null;
1.941 + for (int i = 1; i <= level; ++i)
1.942 + idxs[i] = idx = new Index<K,V>(z, idx, null);
1.943 +
1.944 + HeadIndex<K,V> oldh;
1.945 + int k;
1.946 + for (;;) {
1.947 + oldh = head;
1.948 + int oldLevel = oldh.level;
1.949 + if (level <= oldLevel) { // lost race to add level
1.950 + k = level;
1.951 + break;
1.952 + }
1.953 + HeadIndex<K,V> newh = oldh;
1.954 + Node<K,V> oldbase = oldh.node;
1.955 + for (int j = oldLevel+1; j <= level; ++j)
1.956 + newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);
1.957 + if (casHead(oldh, newh)) {
1.958 + k = oldLevel;
1.959 + break;
1.960 + }
1.961 + }
1.962 + addIndex(idxs[k], oldh, k);
1.963 + }
1.964 + }
1.965 +
1.966 + /**
1.967 + * Adds given index nodes from given level down to 1.
1.968 + * @param idx the topmost index node being inserted
1.969 + * @param h the value of head to use to insert. This must be
1.970 + * snapshotted by callers to provide correct insertion level
1.971 + * @param indexLevel the level of the index
1.972 + */
1.973 + private void addIndex(Index<K,V> idx, HeadIndex<K,V> h, int indexLevel) {
1.974 + // Track next level to insert in case of retries
1.975 + int insertionLevel = indexLevel;
1.976 + Comparable<? super K> key = comparable(idx.node.key);
1.977 + if (key == null) throw new NullPointerException();
1.978 +
1.979 + // Similar to findPredecessor, but adding index nodes along
1.980 + // path to key.
1.981 + for (;;) {
1.982 + int j = h.level;
1.983 + Index<K,V> q = h;
1.984 + Index<K,V> r = q.right;
1.985 + Index<K,V> t = idx;
1.986 + for (;;) {
1.987 + if (r != null) {
1.988 + Node<K,V> n = r.node;
1.989 + // compare before deletion check avoids needing recheck
1.990 + int c = key.compareTo(n.key);
1.991 + if (n.value == null) {
1.992 + if (!q.unlink(r))
1.993 + break;
1.994 + r = q.right;
1.995 + continue;
1.996 + }
1.997 + if (c > 0) {
1.998 + q = r;
1.999 + r = r.right;
1.1000 + continue;
1.1001 + }
1.1002 + }
1.1003 +
1.1004 + if (j == insertionLevel) {
1.1005 + // Don't insert index if node already deleted
1.1006 + if (t.indexesDeletedNode()) {
1.1007 + findNode(key); // cleans up
1.1008 + return;
1.1009 + }
1.1010 + if (!q.link(r, t))
1.1011 + break; // restart
1.1012 + if (--insertionLevel == 0) {
1.1013 + // need final deletion check before return
1.1014 + if (t.indexesDeletedNode())
1.1015 + findNode(key);
1.1016 + return;
1.1017 + }
1.1018 + }
1.1019 +
1.1020 + if (--j >= insertionLevel && j < indexLevel)
1.1021 + t = t.down;
1.1022 + q = q.down;
1.1023 + r = q.right;
1.1024 + }
1.1025 + }
1.1026 + }
1.1027 +
1.1028 + /* ---------------- Deletion -------------- */
1.1029 +
1.1030 + /**
1.1031 + * Main deletion method. Locates node, nulls value, appends a
1.1032 + * deletion marker, unlinks predecessor, removes associated index
1.1033 + * nodes, and possibly reduces head index level.
1.1034 + *
1.1035 + * Index nodes are cleared out simply by calling findPredecessor.
1.1036 + * which unlinks indexes to deleted nodes found along path to key,
1.1037 + * which will include the indexes to this node. This is done
1.1038 + * unconditionally. We can't check beforehand whether there are
1.1039 + * index nodes because it might be the case that some or all
1.1040 + * indexes hadn't been inserted yet for this node during initial
1.1041 + * search for it, and we'd like to ensure lack of garbage
1.1042 + * retention, so must call to be sure.
1.1043 + *
1.1044 + * @param okey the key
1.1045 + * @param value if non-null, the value that must be
1.1046 + * associated with key
1.1047 + * @return the node, or null if not found
1.1048 + */
1.1049 + final V doRemove(Object okey, Object value) {
1.1050 + Comparable<? super K> key = comparable(okey);
1.1051 + for (;;) {
1.1052 + Node<K,V> b = findPredecessor(key);
1.1053 + Node<K,V> n = b.next;
1.1054 + for (;;) {
1.1055 + if (n == null)
1.1056 + return null;
1.1057 + Node<K,V> f = n.next;
1.1058 + if (n != b.next) // inconsistent read
1.1059 + break;
1.1060 + Object v = n.value;
1.1061 + if (v == null) { // n is deleted
1.1062 + n.helpDelete(b, f);
1.1063 + break;
1.1064 + }
1.1065 + if (v == n || b.value == null) // b is deleted
1.1066 + break;
1.1067 + int c = key.compareTo(n.key);
1.1068 + if (c < 0)
1.1069 + return null;
1.1070 + if (c > 0) {
1.1071 + b = n;
1.1072 + n = f;
1.1073 + continue;
1.1074 + }
1.1075 + if (value != null && !value.equals(v))
1.1076 + return null;
1.1077 + if (!n.casValue(v, null))
1.1078 + break;
1.1079 + if (!n.appendMarker(f) || !b.casNext(n, f))
1.1080 + findNode(key); // Retry via findNode
1.1081 + else {
1.1082 + findPredecessor(key); // Clean index
1.1083 + if (head.right == null)
1.1084 + tryReduceLevel();
1.1085 + }
1.1086 + return (V)v;
1.1087 + }
1.1088 + }
1.1089 + }
1.1090 +
1.1091 + /**
1.1092 + * Possibly reduce head level if it has no nodes. This method can
1.1093 + * (rarely) make mistakes, in which case levels can disappear even
1.1094 + * though they are about to contain index nodes. This impacts
1.1095 + * performance, not correctness. To minimize mistakes as well as
1.1096 + * to reduce hysteresis, the level is reduced by one only if the
1.1097 + * topmost three levels look empty. Also, if the removed level
1.1098 + * looks non-empty after CAS, we try to change it back quick
1.1099 + * before anyone notices our mistake! (This trick works pretty
1.1100 + * well because this method will practically never make mistakes
1.1101 + * unless current thread stalls immediately before first CAS, in
1.1102 + * which case it is very unlikely to stall again immediately
1.1103 + * afterwards, so will recover.)
1.1104 + *
1.1105 + * We put up with all this rather than just let levels grow
1.1106 + * because otherwise, even a small map that has undergone a large
1.1107 + * number of insertions and removals will have a lot of levels,
1.1108 + * slowing down access more than would an occasional unwanted
1.1109 + * reduction.
1.1110 + */
1.1111 + private void tryReduceLevel() {
1.1112 + HeadIndex<K,V> h = head;
1.1113 + HeadIndex<K,V> d;
1.1114 + HeadIndex<K,V> e;
1.1115 + if (h.level > 3 &&
1.1116 + (d = (HeadIndex<K,V>)h.down) != null &&
1.1117 + (e = (HeadIndex<K,V>)d.down) != null &&
1.1118 + e.right == null &&
1.1119 + d.right == null &&
1.1120 + h.right == null &&
1.1121 + casHead(h, d) && // try to set
1.1122 + h.right != null) // recheck
1.1123 + casHead(d, h); // try to backout
1.1124 + }
1.1125 +
1.1126 + /* ---------------- Finding and removing first element -------------- */
1.1127 +
1.1128 + /**
1.1129 + * Specialized variant of findNode to get first valid node.
1.1130 + * @return first node or null if empty
1.1131 + */
1.1132 + Node<K,V> findFirst() {
1.1133 + for (;;) {
1.1134 + Node<K,V> b = head.node;
1.1135 + Node<K,V> n = b.next;
1.1136 + if (n == null)
1.1137 + return null;
1.1138 + if (n.value != null)
1.1139 + return n;
1.1140 + n.helpDelete(b, n.next);
1.1141 + }
1.1142 + }
1.1143 +
1.1144 + /**
1.1145 + * Removes first entry; returns its snapshot.
1.1146 + * @return null if empty, else snapshot of first entry
1.1147 + */
1.1148 + Map.Entry<K,V> doRemoveFirstEntry() {
1.1149 + for (;;) {
1.1150 + Node<K,V> b = head.node;
1.1151 + Node<K,V> n = b.next;
1.1152 + if (n == null)
1.1153 + return null;
1.1154 + Node<K,V> f = n.next;
1.1155 + if (n != b.next)
1.1156 + continue;
1.1157 + Object v = n.value;
1.1158 + if (v == null) {
1.1159 + n.helpDelete(b, f);
1.1160 + continue;
1.1161 + }
1.1162 + if (!n.casValue(v, null))
1.1163 + continue;
1.1164 + if (!n.appendMarker(f) || !b.casNext(n, f))
1.1165 + findFirst(); // retry
1.1166 + clearIndexToFirst();
1.1167 + return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, (V)v);
1.1168 + }
1.1169 + }
1.1170 +
1.1171 + /**
1.1172 + * Clears out index nodes associated with deleted first entry.
1.1173 + */
1.1174 + private void clearIndexToFirst() {
1.1175 + for (;;) {
1.1176 + Index<K,V> q = head;
1.1177 + for (;;) {
1.1178 + Index<K,V> r = q.right;
1.1179 + if (r != null && r.indexesDeletedNode() && !q.unlink(r))
1.1180 + break;
1.1181 + if ((q = q.down) == null) {
1.1182 + if (head.right == null)
1.1183 + tryReduceLevel();
1.1184 + return;
1.1185 + }
1.1186 + }
1.1187 + }
1.1188 + }
1.1189 +
1.1190 +
1.1191 + /* ---------------- Finding and removing last element -------------- */
1.1192 +
1.1193 + /**
1.1194 + * Specialized version of find to get last valid node.
1.1195 + * @return last node or null if empty
1.1196 + */
1.1197 + Node<K,V> findLast() {
1.1198 + /*
1.1199 + * findPredecessor can't be used to traverse index level
1.1200 + * because this doesn't use comparisons. So traversals of
1.1201 + * both levels are folded together.
1.1202 + */
1.1203 + Index<K,V> q = head;
1.1204 + for (;;) {
1.1205 + Index<K,V> d, r;
1.1206 + if ((r = q.right) != null) {
1.1207 + if (r.indexesDeletedNode()) {
1.1208 + q.unlink(r);
1.1209 + q = head; // restart
1.1210 + }
1.1211 + else
1.1212 + q = r;
1.1213 + } else if ((d = q.down) != null) {
1.1214 + q = d;
1.1215 + } else {
1.1216 + Node<K,V> b = q.node;
1.1217 + Node<K,V> n = b.next;
1.1218 + for (;;) {
1.1219 + if (n == null)
1.1220 + return b.isBaseHeader() ? null : b;
1.1221 + Node<K,V> f = n.next; // inconsistent read
1.1222 + if (n != b.next)
1.1223 + break;
1.1224 + Object v = n.value;
1.1225 + if (v == null) { // n is deleted
1.1226 + n.helpDelete(b, f);
1.1227 + break;
1.1228 + }
1.1229 + if (v == n || b.value == null) // b is deleted
1.1230 + break;
1.1231 + b = n;
1.1232 + n = f;
1.1233 + }
1.1234 + q = head; // restart
1.1235 + }
1.1236 + }
1.1237 + }
1.1238 +
1.1239 + /**
1.1240 + * Specialized variant of findPredecessor to get predecessor of last
1.1241 + * valid node. Needed when removing the last entry. It is possible
1.1242 + * that all successors of returned node will have been deleted upon
1.1243 + * return, in which case this method can be retried.
1.1244 + * @return likely predecessor of last node
1.1245 + */
1.1246 + private Node<K,V> findPredecessorOfLast() {
1.1247 + for (;;) {
1.1248 + Index<K,V> q = head;
1.1249 + for (;;) {
1.1250 + Index<K,V> d, r;
1.1251 + if ((r = q.right) != null) {
1.1252 + if (r.indexesDeletedNode()) {
1.1253 + q.unlink(r);
1.1254 + break; // must restart
1.1255 + }
1.1256 + // proceed as far across as possible without overshooting
1.1257 + if (r.node.next != null) {
1.1258 + q = r;
1.1259 + continue;
1.1260 + }
1.1261 + }
1.1262 + if ((d = q.down) != null)
1.1263 + q = d;
1.1264 + else
1.1265 + return q.node;
1.1266 + }
1.1267 + }
1.1268 + }
1.1269 +
1.1270 + /**
1.1271 + * Removes last entry; returns its snapshot.
1.1272 + * Specialized variant of doRemove.
1.1273 + * @return null if empty, else snapshot of last entry
1.1274 + */
1.1275 + Map.Entry<K,V> doRemoveLastEntry() {
1.1276 + for (;;) {
1.1277 + Node<K,V> b = findPredecessorOfLast();
1.1278 + Node<K,V> n = b.next;
1.1279 + if (n == null) {
1.1280 + if (b.isBaseHeader()) // empty
1.1281 + return null;
1.1282 + else
1.1283 + continue; // all b's successors are deleted; retry
1.1284 + }
1.1285 + for (;;) {
1.1286 + Node<K,V> f = n.next;
1.1287 + if (n != b.next) // inconsistent read
1.1288 + break;
1.1289 + Object v = n.value;
1.1290 + if (v == null) { // n is deleted
1.1291 + n.helpDelete(b, f);
1.1292 + break;
1.1293 + }
1.1294 + if (v == n || b.value == null) // b is deleted
1.1295 + break;
1.1296 + if (f != null) {
1.1297 + b = n;
1.1298 + n = f;
1.1299 + continue;
1.1300 + }
1.1301 + if (!n.casValue(v, null))
1.1302 + break;
1.1303 + K key = n.key;
1.1304 + Comparable<? super K> ck = comparable(key);
1.1305 + if (!n.appendMarker(f) || !b.casNext(n, f))
1.1306 + findNode(ck); // Retry via findNode
1.1307 + else {
1.1308 + findPredecessor(ck); // Clean index
1.1309 + if (head.right == null)
1.1310 + tryReduceLevel();
1.1311 + }
1.1312 + return new AbstractMap.SimpleImmutableEntry<K,V>(key, (V)v);
1.1313 + }
1.1314 + }
1.1315 + }
1.1316 +
1.1317 + /* ---------------- Relational operations -------------- */
1.1318 +
1.1319 + // Control values OR'ed as arguments to findNear
1.1320 +
1.1321 + private static final int EQ = 1;
1.1322 + private static final int LT = 2;
1.1323 + private static final int GT = 0; // Actually checked as !LT
1.1324 +
1.1325 + /**
1.1326 + * Utility for ceiling, floor, lower, higher methods.
1.1327 + * @param kkey the key
1.1328 + * @param rel the relation -- OR'ed combination of EQ, LT, GT
1.1329 + * @return nearest node fitting relation, or null if no such
1.1330 + */
1.1331 + Node<K,V> findNear(K kkey, int rel) {
1.1332 + Comparable<? super K> key = comparable(kkey);
1.1333 + for (;;) {
1.1334 + Node<K,V> b = findPredecessor(key);
1.1335 + Node<K,V> n = b.next;
1.1336 + for (;;) {
1.1337 + if (n == null)
1.1338 + return ((rel & LT) == 0 || b.isBaseHeader()) ? null : b;
1.1339 + Node<K,V> f = n.next;
1.1340 + if (n != b.next) // inconsistent read
1.1341 + break;
1.1342 + Object v = n.value;
1.1343 + if (v == null) { // n is deleted
1.1344 + n.helpDelete(b, f);
1.1345 + break;
1.1346 + }
1.1347 + if (v == n || b.value == null) // b is deleted
1.1348 + break;
1.1349 + int c = key.compareTo(n.key);
1.1350 + if ((c == 0 && (rel & EQ) != 0) ||
1.1351 + (c < 0 && (rel & LT) == 0))
1.1352 + return n;
1.1353 + if ( c <= 0 && (rel & LT) != 0)
1.1354 + return b.isBaseHeader() ? null : b;
1.1355 + b = n;
1.1356 + n = f;
1.1357 + }
1.1358 + }
1.1359 + }
1.1360 +
1.1361 + /**
1.1362 + * Returns SimpleImmutableEntry for results of findNear.
1.1363 + * @param key the key
1.1364 + * @param rel the relation -- OR'ed combination of EQ, LT, GT
1.1365 + * @return Entry fitting relation, or null if no such
1.1366 + */
1.1367 + AbstractMap.SimpleImmutableEntry<K,V> getNear(K key, int rel) {
1.1368 + for (;;) {
1.1369 + Node<K,V> n = findNear(key, rel);
1.1370 + if (n == null)
1.1371 + return null;
1.1372 + AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
1.1373 + if (e != null)
1.1374 + return e;
1.1375 + }
1.1376 + }
1.1377 +
1.1378 +
1.1379 + /* ---------------- Constructors -------------- */
1.1380 +
1.1381 + /**
1.1382 + * Constructs a new, empty map, sorted according to the
1.1383 + * {@linkplain Comparable natural ordering} of the keys.
1.1384 + */
1.1385 + public ConcurrentSkipListMap() {
1.1386 + this.comparator = null;
1.1387 + initialize();
1.1388 + }
1.1389 +
1.1390 + /**
1.1391 + * Constructs a new, empty map, sorted according to the specified
1.1392 + * comparator.
1.1393 + *
1.1394 + * @param comparator the comparator that will be used to order this map.
1.1395 + * If <tt>null</tt>, the {@linkplain Comparable natural
1.1396 + * ordering} of the keys will be used.
1.1397 + */
1.1398 + public ConcurrentSkipListMap(Comparator<? super K> comparator) {
1.1399 + this.comparator = comparator;
1.1400 + initialize();
1.1401 + }
1.1402 +
1.1403 + /**
1.1404 + * Constructs a new map containing the same mappings as the given map,
1.1405 + * sorted according to the {@linkplain Comparable natural ordering} of
1.1406 + * the keys.
1.1407 + *
1.1408 + * @param m the map whose mappings are to be placed in this map
1.1409 + * @throws ClassCastException if the keys in <tt>m</tt> are not
1.1410 + * {@link Comparable}, or are not mutually comparable
1.1411 + * @throws NullPointerException if the specified map or any of its keys
1.1412 + * or values are null
1.1413 + */
1.1414 + public ConcurrentSkipListMap(Map<? extends K, ? extends V> m) {
1.1415 + this.comparator = null;
1.1416 + initialize();
1.1417 + putAll(m);
1.1418 + }
1.1419 +
1.1420 + /**
1.1421 + * Constructs a new map containing the same mappings and using the
1.1422 + * same ordering as the specified sorted map.
1.1423 + *
1.1424 + * @param m the sorted map whose mappings are to be placed in this
1.1425 + * map, and whose comparator is to be used to sort this map
1.1426 + * @throws NullPointerException if the specified sorted map or any of
1.1427 + * its keys or values are null
1.1428 + */
1.1429 + public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) {
1.1430 + this.comparator = m.comparator();
1.1431 + initialize();
1.1432 + buildFromSorted(m);
1.1433 + }
1.1434 +
1.1435 + /**
1.1436 + * Returns a shallow copy of this <tt>ConcurrentSkipListMap</tt>
1.1437 + * instance. (The keys and values themselves are not cloned.)
1.1438 + *
1.1439 + * @return a shallow copy of this map
1.1440 + */
1.1441 + public ConcurrentSkipListMap<K,V> clone() {
1.1442 + ConcurrentSkipListMap<K,V> clone = null;
1.1443 + try {
1.1444 + clone = (ConcurrentSkipListMap<K,V>) super.clone();
1.1445 + } catch (CloneNotSupportedException e) {
1.1446 + throw new InternalError();
1.1447 + }
1.1448 +
1.1449 + clone.initialize();
1.1450 + clone.buildFromSorted(this);
1.1451 + return clone;
1.1452 + }
1.1453 +
1.1454 + /**
1.1455 + * Streamlined bulk insertion to initialize from elements of
1.1456 + * given sorted map. Call only from constructor or clone
1.1457 + * method.
1.1458 + */
1.1459 + private void buildFromSorted(SortedMap<K, ? extends V> map) {
1.1460 + if (map == null)
1.1461 + throw new NullPointerException();
1.1462 +
1.1463 + HeadIndex<K,V> h = head;
1.1464 + Node<K,V> basepred = h.node;
1.1465 +
1.1466 + // Track the current rightmost node at each level. Uses an
1.1467 + // ArrayList to avoid committing to initial or maximum level.
1.1468 + ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>();
1.1469 +
1.1470 + // initialize
1.1471 + for (int i = 0; i <= h.level; ++i)
1.1472 + preds.add(null);
1.1473 + Index<K,V> q = h;
1.1474 + for (int i = h.level; i > 0; --i) {
1.1475 + preds.set(i, q);
1.1476 + q = q.down;
1.1477 + }
1.1478 +
1.1479 + Iterator<? extends Map.Entry<? extends K, ? extends V>> it =
1.1480 + map.entrySet().iterator();
1.1481 + while (it.hasNext()) {
1.1482 + Map.Entry<? extends K, ? extends V> e = it.next();
1.1483 + int j = randomLevel();
1.1484 + if (j > h.level) j = h.level + 1;
1.1485 + K k = e.getKey();
1.1486 + V v = e.getValue();
1.1487 + if (k == null || v == null)
1.1488 + throw new NullPointerException();
1.1489 + Node<K,V> z = new Node<K,V>(k, v, null);
1.1490 + basepred.next = z;
1.1491 + basepred = z;
1.1492 + if (j > 0) {
1.1493 + Index<K,V> idx = null;
1.1494 + for (int i = 1; i <= j; ++i) {
1.1495 + idx = new Index<K,V>(z, idx, null);
1.1496 + if (i > h.level)
1.1497 + h = new HeadIndex<K,V>(h.node, h, idx, i);
1.1498 +
1.1499 + if (i < preds.size()) {
1.1500 + preds.get(i).right = idx;
1.1501 + preds.set(i, idx);
1.1502 + } else
1.1503 + preds.add(idx);
1.1504 + }
1.1505 + }
1.1506 + }
1.1507 + head = h;
1.1508 + }
1.1509 +
1.1510 + /* ---------------- Serialization -------------- */
1.1511 +
1.1512 + /**
1.1513 + * Save the state of this map to a stream.
1.1514 + *
1.1515 + * @serialData The key (Object) and value (Object) for each
1.1516 + * key-value mapping represented by the map, followed by
1.1517 + * <tt>null</tt>. The key-value mappings are emitted in key-order
1.1518 + * (as determined by the Comparator, or by the keys' natural
1.1519 + * ordering if no Comparator).
1.1520 + */
1.1521 + private void writeObject(java.io.ObjectOutputStream s)
1.1522 + throws java.io.IOException {
1.1523 + // Write out the Comparator and any hidden stuff
1.1524 + s.defaultWriteObject();
1.1525 +
1.1526 + // Write out keys and values (alternating)
1.1527 + for (Node<K,V> n = findFirst(); n != null; n = n.next) {
1.1528 + V v = n.getValidValue();
1.1529 + if (v != null) {
1.1530 + s.writeObject(n.key);
1.1531 + s.writeObject(v);
1.1532 + }
1.1533 + }
1.1534 + s.writeObject(null);
1.1535 + }
1.1536 +
1.1537 + /**
1.1538 + * Reconstitute the map from a stream.
1.1539 + */
1.1540 + private void readObject(final java.io.ObjectInputStream s)
1.1541 + throws java.io.IOException, ClassNotFoundException {
1.1542 + // Read in the Comparator and any hidden stuff
1.1543 + s.defaultReadObject();
1.1544 + // Reset transients
1.1545 + initialize();
1.1546 +
1.1547 + /*
1.1548 + * This is nearly identical to buildFromSorted, but is
1.1549 + * distinct because readObject calls can't be nicely adapted
1.1550 + * as the kind of iterator needed by buildFromSorted. (They
1.1551 + * can be, but doing so requires type cheats and/or creation
1.1552 + * of adaptor classes.) It is simpler to just adapt the code.
1.1553 + */
1.1554 +
1.1555 + HeadIndex<K,V> h = head;
1.1556 + Node<K,V> basepred = h.node;
1.1557 + ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>();
1.1558 + for (int i = 0; i <= h.level; ++i)
1.1559 + preds.add(null);
1.1560 + Index<K,V> q = h;
1.1561 + for (int i = h.level; i > 0; --i) {
1.1562 + preds.set(i, q);
1.1563 + q = q.down;
1.1564 + }
1.1565 +
1.1566 + for (;;) {
1.1567 + Object k = s.readObject();
1.1568 + if (k == null)
1.1569 + break;
1.1570 + Object v = s.readObject();
1.1571 + if (v == null)
1.1572 + throw new NullPointerException();
1.1573 + K key = (K) k;
1.1574 + V val = (V) v;
1.1575 + int j = randomLevel();
1.1576 + if (j > h.level) j = h.level + 1;
1.1577 + Node<K,V> z = new Node<K,V>(key, val, null);
1.1578 + basepred.next = z;
1.1579 + basepred = z;
1.1580 + if (j > 0) {
1.1581 + Index<K,V> idx = null;
1.1582 + for (int i = 1; i <= j; ++i) {
1.1583 + idx = new Index<K,V>(z, idx, null);
1.1584 + if (i > h.level)
1.1585 + h = new HeadIndex<K,V>(h.node, h, idx, i);
1.1586 +
1.1587 + if (i < preds.size()) {
1.1588 + preds.get(i).right = idx;
1.1589 + preds.set(i, idx);
1.1590 + } else
1.1591 + preds.add(idx);
1.1592 + }
1.1593 + }
1.1594 + }
1.1595 + head = h;
1.1596 + }
1.1597 +
1.1598 + /* ------ Map API methods ------ */
1.1599 +
1.1600 + /**
1.1601 + * Returns <tt>true</tt> if this map contains a mapping for the specified
1.1602 + * key.
1.1603 + *
1.1604 + * @param key key whose presence in this map is to be tested
1.1605 + * @return <tt>true</tt> if this map contains a mapping for the specified key
1.1606 + * @throws ClassCastException if the specified key cannot be compared
1.1607 + * with the keys currently in the map
1.1608 + * @throws NullPointerException if the specified key is null
1.1609 + */
1.1610 + public boolean containsKey(Object key) {
1.1611 + return doGet(key) != null;
1.1612 + }
1.1613 +
1.1614 + /**
1.1615 + * Returns the value to which the specified key is mapped,
1.1616 + * or {@code null} if this map contains no mapping for the key.
1.1617 + *
1.1618 + * <p>More formally, if this map contains a mapping from a key
1.1619 + * {@code k} to a value {@code v} such that {@code key} compares
1.1620 + * equal to {@code k} according to the map's ordering, then this
1.1621 + * method returns {@code v}; otherwise it returns {@code null}.
1.1622 + * (There can be at most one such mapping.)
1.1623 + *
1.1624 + * @throws ClassCastException if the specified key cannot be compared
1.1625 + * with the keys currently in the map
1.1626 + * @throws NullPointerException if the specified key is null
1.1627 + */
1.1628 + public V get(Object key) {
1.1629 + return doGet(key);
1.1630 + }
1.1631 +
1.1632 + /**
1.1633 + * Associates the specified value with the specified key in this map.
1.1634 + * If the map previously contained a mapping for the key, the old
1.1635 + * value is replaced.
1.1636 + *
1.1637 + * @param key key with which the specified value is to be associated
1.1638 + * @param value value to be associated with the specified key
1.1639 + * @return the previous value associated with the specified key, or
1.1640 + * <tt>null</tt> if there was no mapping for the key
1.1641 + * @throws ClassCastException if the specified key cannot be compared
1.1642 + * with the keys currently in the map
1.1643 + * @throws NullPointerException if the specified key or value is null
1.1644 + */
1.1645 + public V put(K key, V value) {
1.1646 + if (value == null)
1.1647 + throw new NullPointerException();
1.1648 + return doPut(key, value, false);
1.1649 + }
1.1650 +
1.1651 + /**
1.1652 + * Removes the mapping for the specified key from this map if present.
1.1653 + *
1.1654 + * @param key key for which mapping should be removed
1.1655 + * @return the previous value associated with the specified key, or
1.1656 + * <tt>null</tt> if there was no mapping for the key
1.1657 + * @throws ClassCastException if the specified key cannot be compared
1.1658 + * with the keys currently in the map
1.1659 + * @throws NullPointerException if the specified key is null
1.1660 + */
1.1661 + public V remove(Object key) {
1.1662 + return doRemove(key, null);
1.1663 + }
1.1664 +
1.1665 + /**
1.1666 + * Returns <tt>true</tt> if this map maps one or more keys to the
1.1667 + * specified value. This operation requires time linear in the
1.1668 + * map size. Additionally, it is possible for the map to change
1.1669 + * during execution of this method, in which case the returned
1.1670 + * result may be inaccurate.
1.1671 + *
1.1672 + * @param value value whose presence in this map is to be tested
1.1673 + * @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
1.1674 + * <tt>false</tt> otherwise
1.1675 + * @throws NullPointerException if the specified value is null
1.1676 + */
1.1677 + public boolean containsValue(Object value) {
1.1678 + if (value == null)
1.1679 + throw new NullPointerException();
1.1680 + for (Node<K,V> n = findFirst(); n != null; n = n.next) {
1.1681 + V v = n.getValidValue();
1.1682 + if (v != null && value.equals(v))
1.1683 + return true;
1.1684 + }
1.1685 + return false;
1.1686 + }
1.1687 +
1.1688 + /**
1.1689 + * Returns the number of key-value mappings in this map. If this map
1.1690 + * contains more than <tt>Integer.MAX_VALUE</tt> elements, it
1.1691 + * returns <tt>Integer.MAX_VALUE</tt>.
1.1692 + *
1.1693 + * <p>Beware that, unlike in most collections, this method is
1.1694 + * <em>NOT</em> a constant-time operation. Because of the
1.1695 + * asynchronous nature of these maps, determining the current
1.1696 + * number of elements requires traversing them all to count them.
1.1697 + * Additionally, it is possible for the size to change during
1.1698 + * execution of this method, in which case the returned result
1.1699 + * will be inaccurate. Thus, this method is typically not very
1.1700 + * useful in concurrent applications.
1.1701 + *
1.1702 + * @return the number of elements in this map
1.1703 + */
1.1704 + public int size() {
1.1705 + long count = 0;
1.1706 + for (Node<K,V> n = findFirst(); n != null; n = n.next) {
1.1707 + if (n.getValidValue() != null)
1.1708 + ++count;
1.1709 + }
1.1710 + return (count >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int) count;
1.1711 + }
1.1712 +
1.1713 + /**
1.1714 + * Returns <tt>true</tt> if this map contains no key-value mappings.
1.1715 + * @return <tt>true</tt> if this map contains no key-value mappings
1.1716 + */
1.1717 + public boolean isEmpty() {
1.1718 + return findFirst() == null;
1.1719 + }
1.1720 +
1.1721 + /**
1.1722 + * Removes all of the mappings from this map.
1.1723 + */
1.1724 + public void clear() {
1.1725 + initialize();
1.1726 + }
1.1727 +
1.1728 + /* ---------------- View methods -------------- */
1.1729 +
1.1730 + /*
1.1731 + * Note: Lazy initialization works for views because view classes
1.1732 + * are stateless/immutable so it doesn't matter wrt correctness if
1.1733 + * more than one is created (which will only rarely happen). Even
1.1734 + * so, the following idiom conservatively ensures that the method
1.1735 + * returns the one it created if it does so, not one created by
1.1736 + * another racing thread.
1.1737 + */
1.1738 +
1.1739 + /**
1.1740 + * Returns a {@link NavigableSet} view of the keys contained in this map.
1.1741 + * The set's iterator returns the keys in ascending order.
1.1742 + * The set is backed by the map, so changes to the map are
1.1743 + * reflected in the set, and vice-versa. The set supports element
1.1744 + * removal, which removes the corresponding mapping from the map,
1.1745 + * via the {@code Iterator.remove}, {@code Set.remove},
1.1746 + * {@code removeAll}, {@code retainAll}, and {@code clear}
1.1747 + * operations. It does not support the {@code add} or {@code addAll}
1.1748 + * operations.
1.1749 + *
1.1750 + * <p>The view's {@code iterator} is a "weakly consistent" iterator
1.1751 + * that will never throw {@link ConcurrentModificationException},
1.1752 + * and guarantees to traverse elements as they existed upon
1.1753 + * construction of the iterator, and may (but is not guaranteed to)
1.1754 + * reflect any modifications subsequent to construction.
1.1755 + *
1.1756 + * <p>This method is equivalent to method {@code navigableKeySet}.
1.1757 + *
1.1758 + * @return a navigable set view of the keys in this map
1.1759 + */
1.1760 + public NavigableSet<K> keySet() {
1.1761 + KeySet ks = keySet;
1.1762 + return (ks != null) ? ks : (keySet = new KeySet(this));
1.1763 + }
1.1764 +
1.1765 + public NavigableSet<K> navigableKeySet() {
1.1766 + KeySet ks = keySet;
1.1767 + return (ks != null) ? ks : (keySet = new KeySet(this));
1.1768 + }
1.1769 +
1.1770 + /**
1.1771 + * Returns a {@link Collection} view of the values contained in this map.
1.1772 + * The collection's iterator returns the values in ascending order
1.1773 + * of the corresponding keys.
1.1774 + * The collection is backed by the map, so changes to the map are
1.1775 + * reflected in the collection, and vice-versa. The collection
1.1776 + * supports element removal, which removes the corresponding
1.1777 + * mapping from the map, via the <tt>Iterator.remove</tt>,
1.1778 + * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1.1779 + * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not
1.1780 + * support the <tt>add</tt> or <tt>addAll</tt> operations.
1.1781 + *
1.1782 + * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1.1783 + * that will never throw {@link ConcurrentModificationException},
1.1784 + * and guarantees to traverse elements as they existed upon
1.1785 + * construction of the iterator, and may (but is not guaranteed to)
1.1786 + * reflect any modifications subsequent to construction.
1.1787 + */
1.1788 + public Collection<V> values() {
1.1789 + Values vs = values;
1.1790 + return (vs != null) ? vs : (values = new Values(this));
1.1791 + }
1.1792 +
1.1793 + /**
1.1794 + * Returns a {@link Set} view of the mappings contained in this map.
1.1795 + * The set's iterator returns the entries in ascending key order.
1.1796 + * The set is backed by the map, so changes to the map are
1.1797 + * reflected in the set, and vice-versa. The set supports element
1.1798 + * removal, which removes the corresponding mapping from the map,
1.1799 + * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1.1800 + * <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
1.1801 + * operations. It does not support the <tt>add</tt> or
1.1802 + * <tt>addAll</tt> operations.
1.1803 + *
1.1804 + * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1.1805 + * that will never throw {@link ConcurrentModificationException},
1.1806 + * and guarantees to traverse elements as they existed upon
1.1807 + * construction of the iterator, and may (but is not guaranteed to)
1.1808 + * reflect any modifications subsequent to construction.
1.1809 + *
1.1810 + * <p>The <tt>Map.Entry</tt> elements returned by
1.1811 + * <tt>iterator.next()</tt> do <em>not</em> support the
1.1812 + * <tt>setValue</tt> operation.
1.1813 + *
1.1814 + * @return a set view of the mappings contained in this map,
1.1815 + * sorted in ascending key order
1.1816 + */
1.1817 + public Set<Map.Entry<K,V>> entrySet() {
1.1818 + EntrySet es = entrySet;
1.1819 + return (es != null) ? es : (entrySet = new EntrySet(this));
1.1820 + }
1.1821 +
1.1822 + public ConcurrentNavigableMap<K,V> descendingMap() {
1.1823 + ConcurrentNavigableMap<K,V> dm = descendingMap;
1.1824 + return (dm != null) ? dm : (descendingMap = new SubMap<K,V>
1.1825 + (this, null, false, null, false, true));
1.1826 + }
1.1827 +
1.1828 + public NavigableSet<K> descendingKeySet() {
1.1829 + return descendingMap().navigableKeySet();
1.1830 + }
1.1831 +
1.1832 + /* ---------------- AbstractMap Overrides -------------- */
1.1833 +
1.1834 + /**
1.1835 + * Compares the specified object with this map for equality.
1.1836 + * Returns <tt>true</tt> if the given object is also a map and the
1.1837 + * two maps represent the same mappings. More formally, two maps
1.1838 + * <tt>m1</tt> and <tt>m2</tt> represent the same mappings if
1.1839 + * <tt>m1.entrySet().equals(m2.entrySet())</tt>. This
1.1840 + * operation may return misleading results if either map is
1.1841 + * concurrently modified during execution of this method.
1.1842 + *
1.1843 + * @param o object to be compared for equality with this map
1.1844 + * @return <tt>true</tt> if the specified object is equal to this map
1.1845 + */
1.1846 + public boolean equals(Object o) {
1.1847 + if (o == this)
1.1848 + return true;
1.1849 + if (!(o instanceof Map))
1.1850 + return false;
1.1851 + Map<?,?> m = (Map<?,?>) o;
1.1852 + try {
1.1853 + for (Map.Entry<K,V> e : this.entrySet())
1.1854 + if (! e.getValue().equals(m.get(e.getKey())))
1.1855 + return false;
1.1856 + for (Map.Entry<?,?> e : m.entrySet()) {
1.1857 + Object k = e.getKey();
1.1858 + Object v = e.getValue();
1.1859 + if (k == null || v == null || !v.equals(get(k)))
1.1860 + return false;
1.1861 + }
1.1862 + return true;
1.1863 + } catch (ClassCastException unused) {
1.1864 + return false;
1.1865 + } catch (NullPointerException unused) {
1.1866 + return false;
1.1867 + }
1.1868 + }
1.1869 +
1.1870 + /* ------ ConcurrentMap API methods ------ */
1.1871 +
1.1872 + /**
1.1873 + * {@inheritDoc}
1.1874 + *
1.1875 + * @return the previous value associated with the specified key,
1.1876 + * or <tt>null</tt> if there was no mapping for the key
1.1877 + * @throws ClassCastException if the specified key cannot be compared
1.1878 + * with the keys currently in the map
1.1879 + * @throws NullPointerException if the specified key or value is null
1.1880 + */
1.1881 + public V putIfAbsent(K key, V value) {
1.1882 + if (value == null)
1.1883 + throw new NullPointerException();
1.1884 + return doPut(key, value, true);
1.1885 + }
1.1886 +
1.1887 + /**
1.1888 + * {@inheritDoc}
1.1889 + *
1.1890 + * @throws ClassCastException if the specified key cannot be compared
1.1891 + * with the keys currently in the map
1.1892 + * @throws NullPointerException if the specified key is null
1.1893 + */
1.1894 + public boolean remove(Object key, Object value) {
1.1895 + if (key == null)
1.1896 + throw new NullPointerException();
1.1897 + if (value == null)
1.1898 + return false;
1.1899 + return doRemove(key, value) != null;
1.1900 + }
1.1901 +
1.1902 + /**
1.1903 + * {@inheritDoc}
1.1904 + *
1.1905 + * @throws ClassCastException if the specified key cannot be compared
1.1906 + * with the keys currently in the map
1.1907 + * @throws NullPointerException if any of the arguments are null
1.1908 + */
1.1909 + public boolean replace(K key, V oldValue, V newValue) {
1.1910 + if (oldValue == null || newValue == null)
1.1911 + throw new NullPointerException();
1.1912 + Comparable<? super K> k = comparable(key);
1.1913 + for (;;) {
1.1914 + Node<K,V> n = findNode(k);
1.1915 + if (n == null)
1.1916 + return false;
1.1917 + Object v = n.value;
1.1918 + if (v != null) {
1.1919 + if (!oldValue.equals(v))
1.1920 + return false;
1.1921 + if (n.casValue(v, newValue))
1.1922 + return true;
1.1923 + }
1.1924 + }
1.1925 + }
1.1926 +
1.1927 + /**
1.1928 + * {@inheritDoc}
1.1929 + *
1.1930 + * @return the previous value associated with the specified key,
1.1931 + * or <tt>null</tt> if there was no mapping for the key
1.1932 + * @throws ClassCastException if the specified key cannot be compared
1.1933 + * with the keys currently in the map
1.1934 + * @throws NullPointerException if the specified key or value is null
1.1935 + */
1.1936 + public V replace(K key, V value) {
1.1937 + if (value == null)
1.1938 + throw new NullPointerException();
1.1939 + Comparable<? super K> k = comparable(key);
1.1940 + for (;;) {
1.1941 + Node<K,V> n = findNode(k);
1.1942 + if (n == null)
1.1943 + return null;
1.1944 + Object v = n.value;
1.1945 + if (v != null && n.casValue(v, value))
1.1946 + return (V)v;
1.1947 + }
1.1948 + }
1.1949 +
1.1950 + /* ------ SortedMap API methods ------ */
1.1951 +
1.1952 + public Comparator<? super K> comparator() {
1.1953 + return comparator;
1.1954 + }
1.1955 +
1.1956 + /**
1.1957 + * @throws NoSuchElementException {@inheritDoc}
1.1958 + */
1.1959 + public K firstKey() {
1.1960 + Node<K,V> n = findFirst();
1.1961 + if (n == null)
1.1962 + throw new NoSuchElementException();
1.1963 + return n.key;
1.1964 + }
1.1965 +
1.1966 + /**
1.1967 + * @throws NoSuchElementException {@inheritDoc}
1.1968 + */
1.1969 + public K lastKey() {
1.1970 + Node<K,V> n = findLast();
1.1971 + if (n == null)
1.1972 + throw new NoSuchElementException();
1.1973 + return n.key;
1.1974 + }
1.1975 +
1.1976 + /**
1.1977 + * @throws ClassCastException {@inheritDoc}
1.1978 + * @throws NullPointerException if {@code fromKey} or {@code toKey} is null
1.1979 + * @throws IllegalArgumentException {@inheritDoc}
1.1980 + */
1.1981 + public ConcurrentNavigableMap<K,V> subMap(K fromKey,
1.1982 + boolean fromInclusive,
1.1983 + K toKey,
1.1984 + boolean toInclusive) {
1.1985 + if (fromKey == null || toKey == null)
1.1986 + throw new NullPointerException();
1.1987 + return new SubMap<K,V>
1.1988 + (this, fromKey, fromInclusive, toKey, toInclusive, false);
1.1989 + }
1.1990 +
1.1991 + /**
1.1992 + * @throws ClassCastException {@inheritDoc}
1.1993 + * @throws NullPointerException if {@code toKey} is null
1.1994 + * @throws IllegalArgumentException {@inheritDoc}
1.1995 + */
1.1996 + public ConcurrentNavigableMap<K,V> headMap(K toKey,
1.1997 + boolean inclusive) {
1.1998 + if (toKey == null)
1.1999 + throw new NullPointerException();
1.2000 + return new SubMap<K,V>
1.2001 + (this, null, false, toKey, inclusive, false);
1.2002 + }
1.2003 +
1.2004 + /**
1.2005 + * @throws ClassCastException {@inheritDoc}
1.2006 + * @throws NullPointerException if {@code fromKey} is null
1.2007 + * @throws IllegalArgumentException {@inheritDoc}
1.2008 + */
1.2009 + public ConcurrentNavigableMap<K,V> tailMap(K fromKey,
1.2010 + boolean inclusive) {
1.2011 + if (fromKey == null)
1.2012 + throw new NullPointerException();
1.2013 + return new SubMap<K,V>
1.2014 + (this, fromKey, inclusive, null, false, false);
1.2015 + }
1.2016 +
1.2017 + /**
1.2018 + * @throws ClassCastException {@inheritDoc}
1.2019 + * @throws NullPointerException if {@code fromKey} or {@code toKey} is null
1.2020 + * @throws IllegalArgumentException {@inheritDoc}
1.2021 + */
1.2022 + public ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey) {
1.2023 + return subMap(fromKey, true, toKey, false);
1.2024 + }
1.2025 +
1.2026 + /**
1.2027 + * @throws ClassCastException {@inheritDoc}
1.2028 + * @throws NullPointerException if {@code toKey} is null
1.2029 + * @throws IllegalArgumentException {@inheritDoc}
1.2030 + */
1.2031 + public ConcurrentNavigableMap<K,V> headMap(K toKey) {
1.2032 + return headMap(toKey, false);
1.2033 + }
1.2034 +
1.2035 + /**
1.2036 + * @throws ClassCastException {@inheritDoc}
1.2037 + * @throws NullPointerException if {@code fromKey} is null
1.2038 + * @throws IllegalArgumentException {@inheritDoc}
1.2039 + */
1.2040 + public ConcurrentNavigableMap<K,V> tailMap(K fromKey) {
1.2041 + return tailMap(fromKey, true);
1.2042 + }
1.2043 +
1.2044 + /* ---------------- Relational operations -------------- */
1.2045 +
1.2046 + /**
1.2047 + * Returns a key-value mapping associated with the greatest key
1.2048 + * strictly less than the given key, or <tt>null</tt> if there is
1.2049 + * no such key. The returned entry does <em>not</em> support the
1.2050 + * <tt>Entry.setValue</tt> method.
1.2051 + *
1.2052 + * @throws ClassCastException {@inheritDoc}
1.2053 + * @throws NullPointerException if the specified key is null
1.2054 + */
1.2055 + public Map.Entry<K,V> lowerEntry(K key) {
1.2056 + return getNear(key, LT);
1.2057 + }
1.2058 +
1.2059 + /**
1.2060 + * @throws ClassCastException {@inheritDoc}
1.2061 + * @throws NullPointerException if the specified key is null
1.2062 + */
1.2063 + public K lowerKey(K key) {
1.2064 + Node<K,V> n = findNear(key, LT);
1.2065 + return (n == null) ? null : n.key;
1.2066 + }
1.2067 +
1.2068 + /**
1.2069 + * Returns a key-value mapping associated with the greatest key
1.2070 + * less than or equal to the given key, or <tt>null</tt> if there
1.2071 + * is no such key. The returned entry does <em>not</em> support
1.2072 + * the <tt>Entry.setValue</tt> method.
1.2073 + *
1.2074 + * @param key the key
1.2075 + * @throws ClassCastException {@inheritDoc}
1.2076 + * @throws NullPointerException if the specified key is null
1.2077 + */
1.2078 + public Map.Entry<K,V> floorEntry(K key) {
1.2079 + return getNear(key, LT|EQ);
1.2080 + }
1.2081 +
1.2082 + /**
1.2083 + * @param key the key
1.2084 + * @throws ClassCastException {@inheritDoc}
1.2085 + * @throws NullPointerException if the specified key is null
1.2086 + */
1.2087 + public K floorKey(K key) {
1.2088 + Node<K,V> n = findNear(key, LT|EQ);
1.2089 + return (n == null) ? null : n.key;
1.2090 + }
1.2091 +
1.2092 + /**
1.2093 + * Returns a key-value mapping associated with the least key
1.2094 + * greater than or equal to the given key, or <tt>null</tt> if
1.2095 + * there is no such entry. The returned entry does <em>not</em>
1.2096 + * support the <tt>Entry.setValue</tt> method.
1.2097 + *
1.2098 + * @throws ClassCastException {@inheritDoc}
1.2099 + * @throws NullPointerException if the specified key is null
1.2100 + */
1.2101 + public Map.Entry<K,V> ceilingEntry(K key) {
1.2102 + return getNear(key, GT|EQ);
1.2103 + }
1.2104 +
1.2105 + /**
1.2106 + * @throws ClassCastException {@inheritDoc}
1.2107 + * @throws NullPointerException if the specified key is null
1.2108 + */
1.2109 + public K ceilingKey(K key) {
1.2110 + Node<K,V> n = findNear(key, GT|EQ);
1.2111 + return (n == null) ? null : n.key;
1.2112 + }
1.2113 +
1.2114 + /**
1.2115 + * Returns a key-value mapping associated with the least key
1.2116 + * strictly greater than the given key, or <tt>null</tt> if there
1.2117 + * is no such key. The returned entry does <em>not</em> support
1.2118 + * the <tt>Entry.setValue</tt> method.
1.2119 + *
1.2120 + * @param key the key
1.2121 + * @throws ClassCastException {@inheritDoc}
1.2122 + * @throws NullPointerException if the specified key is null
1.2123 + */
1.2124 + public Map.Entry<K,V> higherEntry(K key) {
1.2125 + return getNear(key, GT);
1.2126 + }
1.2127 +
1.2128 + /**
1.2129 + * @param key the key
1.2130 + * @throws ClassCastException {@inheritDoc}
1.2131 + * @throws NullPointerException if the specified key is null
1.2132 + */
1.2133 + public K higherKey(K key) {
1.2134 + Node<K,V> n = findNear(key, GT);
1.2135 + return (n == null) ? null : n.key;
1.2136 + }
1.2137 +
1.2138 + /**
1.2139 + * Returns a key-value mapping associated with the least
1.2140 + * key in this map, or <tt>null</tt> if the map is empty.
1.2141 + * The returned entry does <em>not</em> support
1.2142 + * the <tt>Entry.setValue</tt> method.
1.2143 + */
1.2144 + public Map.Entry<K,V> firstEntry() {
1.2145 + for (;;) {
1.2146 + Node<K,V> n = findFirst();
1.2147 + if (n == null)
1.2148 + return null;
1.2149 + AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
1.2150 + if (e != null)
1.2151 + return e;
1.2152 + }
1.2153 + }
1.2154 +
1.2155 + /**
1.2156 + * Returns a key-value mapping associated with the greatest
1.2157 + * key in this map, or <tt>null</tt> if the map is empty.
1.2158 + * The returned entry does <em>not</em> support
1.2159 + * the <tt>Entry.setValue</tt> method.
1.2160 + */
1.2161 + public Map.Entry<K,V> lastEntry() {
1.2162 + for (;;) {
1.2163 + Node<K,V> n = findLast();
1.2164 + if (n == null)
1.2165 + return null;
1.2166 + AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
1.2167 + if (e != null)
1.2168 + return e;
1.2169 + }
1.2170 + }
1.2171 +
1.2172 + /**
1.2173 + * Removes and returns a key-value mapping associated with
1.2174 + * the least key in this map, or <tt>null</tt> if the map is empty.
1.2175 + * The returned entry does <em>not</em> support
1.2176 + * the <tt>Entry.setValue</tt> method.
1.2177 + */
1.2178 + public Map.Entry<K,V> pollFirstEntry() {
1.2179 + return doRemoveFirstEntry();
1.2180 + }
1.2181 +
1.2182 + /**
1.2183 + * Removes and returns a key-value mapping associated with
1.2184 + * the greatest key in this map, or <tt>null</tt> if the map is empty.
1.2185 + * The returned entry does <em>not</em> support
1.2186 + * the <tt>Entry.setValue</tt> method.
1.2187 + */
1.2188 + public Map.Entry<K,V> pollLastEntry() {
1.2189 + return doRemoveLastEntry();
1.2190 + }
1.2191 +
1.2192 +
1.2193 + /* ---------------- Iterators -------------- */
1.2194 +
1.2195 + /**
1.2196 + * Base of iterator classes:
1.2197 + */
1.2198 + abstract class Iter<T> implements Iterator<T> {
1.2199 + /** the last node returned by next() */
1.2200 + Node<K,V> lastReturned;
1.2201 + /** the next node to return from next(); */
1.2202 + Node<K,V> next;
1.2203 + /** Cache of next value field to maintain weak consistency */
1.2204 + V nextValue;
1.2205 +
1.2206 + /** Initializes ascending iterator for entire range. */
1.2207 + Iter() {
1.2208 + for (;;) {
1.2209 + next = findFirst();
1.2210 + if (next == null)
1.2211 + break;
1.2212 + Object x = next.value;
1.2213 + if (x != null && x != next) {
1.2214 + nextValue = (V) x;
1.2215 + break;
1.2216 + }
1.2217 + }
1.2218 + }
1.2219 +
1.2220 + public final boolean hasNext() {
1.2221 + return next != null;
1.2222 + }
1.2223 +
1.2224 + /** Advances next to higher entry. */
1.2225 + final void advance() {
1.2226 + if (next == null)
1.2227 + throw new NoSuchElementException();
1.2228 + lastReturned = next;
1.2229 + for (;;) {
1.2230 + next = next.next;
1.2231 + if (next == null)
1.2232 + break;
1.2233 + Object x = next.value;
1.2234 + if (x != null && x != next) {
1.2235 + nextValue = (V) x;
1.2236 + break;
1.2237 + }
1.2238 + }
1.2239 + }
1.2240 +
1.2241 + public void remove() {
1.2242 + Node<K,V> l = lastReturned;
1.2243 + if (l == null)
1.2244 + throw new IllegalStateException();
1.2245 + // It would not be worth all of the overhead to directly
1.2246 + // unlink from here. Using remove is fast enough.
1.2247 + ConcurrentSkipListMap.this.remove(l.key);
1.2248 + lastReturned = null;
1.2249 + }
1.2250 +
1.2251 + }
1.2252 +
1.2253 + final class ValueIterator extends Iter<V> {
1.2254 + public V next() {
1.2255 + V v = nextValue;
1.2256 + advance();
1.2257 + return v;
1.2258 + }
1.2259 + }
1.2260 +
1.2261 + final class KeyIterator extends Iter<K> {
1.2262 + public K next() {
1.2263 + Node<K,V> n = next;
1.2264 + advance();
1.2265 + return n.key;
1.2266 + }
1.2267 + }
1.2268 +
1.2269 + final class EntryIterator extends Iter<Map.Entry<K,V>> {
1.2270 + public Map.Entry<K,V> next() {
1.2271 + Node<K,V> n = next;
1.2272 + V v = nextValue;
1.2273 + advance();
1.2274 + return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
1.2275 + }
1.2276 + }
1.2277 +
1.2278 + // Factory methods for iterators needed by ConcurrentSkipListSet etc
1.2279 +
1.2280 + Iterator<K> keyIterator() {
1.2281 + return new KeyIterator();
1.2282 + }
1.2283 +
1.2284 + Iterator<V> valueIterator() {
1.2285 + return new ValueIterator();
1.2286 + }
1.2287 +
1.2288 + Iterator<Map.Entry<K,V>> entryIterator() {
1.2289 + return new EntryIterator();
1.2290 + }
1.2291 +
1.2292 + /* ---------------- View Classes -------------- */
1.2293 +
1.2294 + /*
1.2295 + * View classes are static, delegating to a ConcurrentNavigableMap
1.2296 + * to allow use by SubMaps, which outweighs the ugliness of
1.2297 + * needing type-tests for Iterator methods.
1.2298 + */
1.2299 +
1.2300 + static final <E> List<E> toList(Collection<E> c) {
1.2301 + // Using size() here would be a pessimization.
1.2302 + List<E> list = new ArrayList<E>();
1.2303 + for (E e : c)
1.2304 + list.add(e);
1.2305 + return list;
1.2306 + }
1.2307 +
1.2308 + static final class KeySet<E>
1.2309 + extends AbstractSet<E> implements NavigableSet<E> {
1.2310 + private final ConcurrentNavigableMap<E,Object> m;
1.2311 + KeySet(ConcurrentNavigableMap<E,Object> map) { m = map; }
1.2312 + public int size() { return m.size(); }
1.2313 + public boolean isEmpty() { return m.isEmpty(); }
1.2314 + public boolean contains(Object o) { return m.containsKey(o); }
1.2315 + public boolean remove(Object o) { return m.remove(o) != null; }
1.2316 + public void clear() { m.clear(); }
1.2317 + public E lower(E e) { return m.lowerKey(e); }
1.2318 + public E floor(E e) { return m.floorKey(e); }
1.2319 + public E ceiling(E e) { return m.ceilingKey(e); }
1.2320 + public E higher(E e) { return m.higherKey(e); }
1.2321 + public Comparator<? super E> comparator() { return m.comparator(); }
1.2322 + public E first() { return m.firstKey(); }
1.2323 + public E last() { return m.lastKey(); }
1.2324 + public E pollFirst() {
1.2325 + Map.Entry<E,Object> e = m.pollFirstEntry();
1.2326 + return (e == null) ? null : e.getKey();
1.2327 + }
1.2328 + public E pollLast() {
1.2329 + Map.Entry<E,Object> e = m.pollLastEntry();
1.2330 + return (e == null) ? null : e.getKey();
1.2331 + }
1.2332 + public Iterator<E> iterator() {
1.2333 + if (m instanceof ConcurrentSkipListMap)
1.2334 + return ((ConcurrentSkipListMap<E,Object>)m).keyIterator();
1.2335 + else
1.2336 + return ((ConcurrentSkipListMap.SubMap<E,Object>)m).keyIterator();
1.2337 + }
1.2338 + public boolean equals(Object o) {
1.2339 + if (o == this)
1.2340 + return true;
1.2341 + if (!(o instanceof Set))
1.2342 + return false;
1.2343 + Collection<?> c = (Collection<?>) o;
1.2344 + try {
1.2345 + return containsAll(c) && c.containsAll(this);
1.2346 + } catch (ClassCastException unused) {
1.2347 + return false;
1.2348 + } catch (NullPointerException unused) {
1.2349 + return false;
1.2350 + }
1.2351 + }
1.2352 + public Object[] toArray() { return toList(this).toArray(); }
1.2353 + public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
1.2354 + public Iterator<E> descendingIterator() {
1.2355 + return descendingSet().iterator();
1.2356 + }
1.2357 + public NavigableSet<E> subSet(E fromElement,
1.2358 + boolean fromInclusive,
1.2359 + E toElement,
1.2360 + boolean toInclusive) {
1.2361 + return new KeySet<E>(m.subMap(fromElement, fromInclusive,
1.2362 + toElement, toInclusive));
1.2363 + }
1.2364 + public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1.2365 + return new KeySet<E>(m.headMap(toElement, inclusive));
1.2366 + }
1.2367 + public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1.2368 + return new KeySet<E>(m.tailMap(fromElement, inclusive));
1.2369 + }
1.2370 + public NavigableSet<E> subSet(E fromElement, E toElement) {
1.2371 + return subSet(fromElement, true, toElement, false);
1.2372 + }
1.2373 + public NavigableSet<E> headSet(E toElement) {
1.2374 + return headSet(toElement, false);
1.2375 + }
1.2376 + public NavigableSet<E> tailSet(E fromElement) {
1.2377 + return tailSet(fromElement, true);
1.2378 + }
1.2379 + public NavigableSet<E> descendingSet() {
1.2380 + return new KeySet(m.descendingMap());
1.2381 + }
1.2382 + }
1.2383 +
1.2384 + static final class Values<E> extends AbstractCollection<E> {
1.2385 + private final ConcurrentNavigableMap<Object, E> m;
1.2386 + Values(ConcurrentNavigableMap<Object, E> map) {
1.2387 + m = map;
1.2388 + }
1.2389 + public Iterator<E> iterator() {
1.2390 + if (m instanceof ConcurrentSkipListMap)
1.2391 + return ((ConcurrentSkipListMap<Object,E>)m).valueIterator();
1.2392 + else
1.2393 + return ((SubMap<Object,E>)m).valueIterator();
1.2394 + }
1.2395 + public boolean isEmpty() {
1.2396 + return m.isEmpty();
1.2397 + }
1.2398 + public int size() {
1.2399 + return m.size();
1.2400 + }
1.2401 + public boolean contains(Object o) {
1.2402 + return m.containsValue(o);
1.2403 + }
1.2404 + public void clear() {
1.2405 + m.clear();
1.2406 + }
1.2407 + public Object[] toArray() { return toList(this).toArray(); }
1.2408 + public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
1.2409 + }
1.2410 +
1.2411 + static final class EntrySet<K1,V1> extends AbstractSet<Map.Entry<K1,V1>> {
1.2412 + private final ConcurrentNavigableMap<K1, V1> m;
1.2413 + EntrySet(ConcurrentNavigableMap<K1, V1> map) {
1.2414 + m = map;
1.2415 + }
1.2416 +
1.2417 + public Iterator<Map.Entry<K1,V1>> iterator() {
1.2418 + if (m instanceof ConcurrentSkipListMap)
1.2419 + return ((ConcurrentSkipListMap<K1,V1>)m).entryIterator();
1.2420 + else
1.2421 + return ((SubMap<K1,V1>)m).entryIterator();
1.2422 + }
1.2423 +
1.2424 + public boolean contains(Object o) {
1.2425 + if (!(o instanceof Map.Entry))
1.2426 + return false;
1.2427 + Map.Entry<K1,V1> e = (Map.Entry<K1,V1>)o;
1.2428 + V1 v = m.get(e.getKey());
1.2429 + return v != null && v.equals(e.getValue());
1.2430 + }
1.2431 + public boolean remove(Object o) {
1.2432 + if (!(o instanceof Map.Entry))
1.2433 + return false;
1.2434 + Map.Entry<K1,V1> e = (Map.Entry<K1,V1>)o;
1.2435 + return m.remove(e.getKey(),
1.2436 + e.getValue());
1.2437 + }
1.2438 + public boolean isEmpty() {
1.2439 + return m.isEmpty();
1.2440 + }
1.2441 + public int size() {
1.2442 + return m.size();
1.2443 + }
1.2444 + public void clear() {
1.2445 + m.clear();
1.2446 + }
1.2447 + public boolean equals(Object o) {
1.2448 + if (o == this)
1.2449 + return true;
1.2450 + if (!(o instanceof Set))
1.2451 + return false;
1.2452 + Collection<?> c = (Collection<?>) o;
1.2453 + try {
1.2454 + return containsAll(c) && c.containsAll(this);
1.2455 + } catch (ClassCastException unused) {
1.2456 + return false;
1.2457 + } catch (NullPointerException unused) {
1.2458 + return false;
1.2459 + }
1.2460 + }
1.2461 + public Object[] toArray() { return toList(this).toArray(); }
1.2462 + public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
1.2463 + }
1.2464 +
1.2465 + /**
1.2466 + * Submaps returned by {@link ConcurrentSkipListMap} submap operations
1.2467 + * represent a subrange of mappings of their underlying
1.2468 + * maps. Instances of this class support all methods of their
1.2469 + * underlying maps, differing in that mappings outside their range are
1.2470 + * ignored, and attempts to add mappings outside their ranges result
1.2471 + * in {@link IllegalArgumentException}. Instances of this class are
1.2472 + * constructed only using the <tt>subMap</tt>, <tt>headMap</tt>, and
1.2473 + * <tt>tailMap</tt> methods of their underlying maps.
1.2474 + *
1.2475 + * @serial include
1.2476 + */
1.2477 + static final class SubMap<K,V> extends AbstractMap<K,V>
1.2478 + implements ConcurrentNavigableMap<K,V>, Cloneable,
1.2479 + java.io.Serializable {
1.2480 + private static final long serialVersionUID = -7647078645895051609L;
1.2481 +
1.2482 + /** Underlying map */
1.2483 + private final ConcurrentSkipListMap<K,V> m;
1.2484 + /** lower bound key, or null if from start */
1.2485 + private final K lo;
1.2486 + /** upper bound key, or null if to end */
1.2487 + private final K hi;
1.2488 + /** inclusion flag for lo */
1.2489 + private final boolean loInclusive;
1.2490 + /** inclusion flag for hi */
1.2491 + private final boolean hiInclusive;
1.2492 + /** direction */
1.2493 + private final boolean isDescending;
1.2494 +
1.2495 + // Lazily initialized view holders
1.2496 + private transient KeySet<K> keySetView;
1.2497 + private transient Set<Map.Entry<K,V>> entrySetView;
1.2498 + private transient Collection<V> valuesView;
1.2499 +
1.2500 + /**
1.2501 + * Creates a new submap, initializing all fields
1.2502 + */
1.2503 + SubMap(ConcurrentSkipListMap<K,V> map,
1.2504 + K fromKey, boolean fromInclusive,
1.2505 + K toKey, boolean toInclusive,
1.2506 + boolean isDescending) {
1.2507 + if (fromKey != null && toKey != null &&
1.2508 + map.compare(fromKey, toKey) > 0)
1.2509 + throw new IllegalArgumentException("inconsistent range");
1.2510 + this.m = map;
1.2511 + this.lo = fromKey;
1.2512 + this.hi = toKey;
1.2513 + this.loInclusive = fromInclusive;
1.2514 + this.hiInclusive = toInclusive;
1.2515 + this.isDescending = isDescending;
1.2516 + }
1.2517 +
1.2518 + /* ---------------- Utilities -------------- */
1.2519 +
1.2520 + private boolean tooLow(K key) {
1.2521 + if (lo != null) {
1.2522 + int c = m.compare(key, lo);
1.2523 + if (c < 0 || (c == 0 && !loInclusive))
1.2524 + return true;
1.2525 + }
1.2526 + return false;
1.2527 + }
1.2528 +
1.2529 + private boolean tooHigh(K key) {
1.2530 + if (hi != null) {
1.2531 + int c = m.compare(key, hi);
1.2532 + if (c > 0 || (c == 0 && !hiInclusive))
1.2533 + return true;
1.2534 + }
1.2535 + return false;
1.2536 + }
1.2537 +
1.2538 + private boolean inBounds(K key) {
1.2539 + return !tooLow(key) && !tooHigh(key);
1.2540 + }
1.2541 +
1.2542 + private void checkKeyBounds(K key) throws IllegalArgumentException {
1.2543 + if (key == null)
1.2544 + throw new NullPointerException();
1.2545 + if (!inBounds(key))
1.2546 + throw new IllegalArgumentException("key out of range");
1.2547 + }
1.2548 +
1.2549 + /**
1.2550 + * Returns true if node key is less than upper bound of range
1.2551 + */
1.2552 + private boolean isBeforeEnd(ConcurrentSkipListMap.Node<K,V> n) {
1.2553 + if (n == null)
1.2554 + return false;
1.2555 + if (hi == null)
1.2556 + return true;
1.2557 + K k = n.key;
1.2558 + if (k == null) // pass by markers and headers
1.2559 + return true;
1.2560 + int c = m.compare(k, hi);
1.2561 + if (c > 0 || (c == 0 && !hiInclusive))
1.2562 + return false;
1.2563 + return true;
1.2564 + }
1.2565 +
1.2566 + /**
1.2567 + * Returns lowest node. This node might not be in range, so
1.2568 + * most usages need to check bounds
1.2569 + */
1.2570 + private ConcurrentSkipListMap.Node<K,V> loNode() {
1.2571 + if (lo == null)
1.2572 + return m.findFirst();
1.2573 + else if (loInclusive)
1.2574 + return m.findNear(lo, m.GT|m.EQ);
1.2575 + else
1.2576 + return m.findNear(lo, m.GT);
1.2577 + }
1.2578 +
1.2579 + /**
1.2580 + * Returns highest node. This node might not be in range, so
1.2581 + * most usages need to check bounds
1.2582 + */
1.2583 + private ConcurrentSkipListMap.Node<K,V> hiNode() {
1.2584 + if (hi == null)
1.2585 + return m.findLast();
1.2586 + else if (hiInclusive)
1.2587 + return m.findNear(hi, m.LT|m.EQ);
1.2588 + else
1.2589 + return m.findNear(hi, m.LT);
1.2590 + }
1.2591 +
1.2592 + /**
1.2593 + * Returns lowest absolute key (ignoring directonality)
1.2594 + */
1.2595 + private K lowestKey() {
1.2596 + ConcurrentSkipListMap.Node<K,V> n = loNode();
1.2597 + if (isBeforeEnd(n))
1.2598 + return n.key;
1.2599 + else
1.2600 + throw new NoSuchElementException();
1.2601 + }
1.2602 +
1.2603 + /**
1.2604 + * Returns highest absolute key (ignoring directonality)
1.2605 + */
1.2606 + private K highestKey() {
1.2607 + ConcurrentSkipListMap.Node<K,V> n = hiNode();
1.2608 + if (n != null) {
1.2609 + K last = n.key;
1.2610 + if (inBounds(last))
1.2611 + return last;
1.2612 + }
1.2613 + throw new NoSuchElementException();
1.2614 + }
1.2615 +
1.2616 + private Map.Entry<K,V> lowestEntry() {
1.2617 + for (;;) {
1.2618 + ConcurrentSkipListMap.Node<K,V> n = loNode();
1.2619 + if (!isBeforeEnd(n))
1.2620 + return null;
1.2621 + Map.Entry<K,V> e = n.createSnapshot();
1.2622 + if (e != null)
1.2623 + return e;
1.2624 + }
1.2625 + }
1.2626 +
1.2627 + private Map.Entry<K,V> highestEntry() {
1.2628 + for (;;) {
1.2629 + ConcurrentSkipListMap.Node<K,V> n = hiNode();
1.2630 + if (n == null || !inBounds(n.key))
1.2631 + return null;
1.2632 + Map.Entry<K,V> e = n.createSnapshot();
1.2633 + if (e != null)
1.2634 + return e;
1.2635 + }
1.2636 + }
1.2637 +
1.2638 + private Map.Entry<K,V> removeLowest() {
1.2639 + for (;;) {
1.2640 + Node<K,V> n = loNode();
1.2641 + if (n == null)
1.2642 + return null;
1.2643 + K k = n.key;
1.2644 + if (!inBounds(k))
1.2645 + return null;
1.2646 + V v = m.doRemove(k, null);
1.2647 + if (v != null)
1.2648 + return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
1.2649 + }
1.2650 + }
1.2651 +
1.2652 + private Map.Entry<K,V> removeHighest() {
1.2653 + for (;;) {
1.2654 + Node<K,V> n = hiNode();
1.2655 + if (n == null)
1.2656 + return null;
1.2657 + K k = n.key;
1.2658 + if (!inBounds(k))
1.2659 + return null;
1.2660 + V v = m.doRemove(k, null);
1.2661 + if (v != null)
1.2662 + return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
1.2663 + }
1.2664 + }
1.2665 +
1.2666 + /**
1.2667 + * Submap version of ConcurrentSkipListMap.getNearEntry
1.2668 + */
1.2669 + private Map.Entry<K,V> getNearEntry(K key, int rel) {
1.2670 + if (isDescending) { // adjust relation for direction
1.2671 + if ((rel & m.LT) == 0)
1.2672 + rel |= m.LT;
1.2673 + else
1.2674 + rel &= ~m.LT;
1.2675 + }
1.2676 + if (tooLow(key))
1.2677 + return ((rel & m.LT) != 0) ? null : lowestEntry();
1.2678 + if (tooHigh(key))
1.2679 + return ((rel & m.LT) != 0) ? highestEntry() : null;
1.2680 + for (;;) {
1.2681 + Node<K,V> n = m.findNear(key, rel);
1.2682 + if (n == null || !inBounds(n.key))
1.2683 + return null;
1.2684 + K k = n.key;
1.2685 + V v = n.getValidValue();
1.2686 + if (v != null)
1.2687 + return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
1.2688 + }
1.2689 + }
1.2690 +
1.2691 + // Almost the same as getNearEntry, except for keys
1.2692 + private K getNearKey(K key, int rel) {
1.2693 + if (isDescending) { // adjust relation for direction
1.2694 + if ((rel & m.LT) == 0)
1.2695 + rel |= m.LT;
1.2696 + else
1.2697 + rel &= ~m.LT;
1.2698 + }
1.2699 + if (tooLow(key)) {
1.2700 + if ((rel & m.LT) == 0) {
1.2701 + ConcurrentSkipListMap.Node<K,V> n = loNode();
1.2702 + if (isBeforeEnd(n))
1.2703 + return n.key;
1.2704 + }
1.2705 + return null;
1.2706 + }
1.2707 + if (tooHigh(key)) {
1.2708 + if ((rel & m.LT) != 0) {
1.2709 + ConcurrentSkipListMap.Node<K,V> n = hiNode();
1.2710 + if (n != null) {
1.2711 + K last = n.key;
1.2712 + if (inBounds(last))
1.2713 + return last;
1.2714 + }
1.2715 + }
1.2716 + return null;
1.2717 + }
1.2718 + for (;;) {
1.2719 + Node<K,V> n = m.findNear(key, rel);
1.2720 + if (n == null || !inBounds(n.key))
1.2721 + return null;
1.2722 + K k = n.key;
1.2723 + V v = n.getValidValue();
1.2724 + if (v != null)
1.2725 + return k;
1.2726 + }
1.2727 + }
1.2728 +
1.2729 + /* ---------------- Map API methods -------------- */
1.2730 +
1.2731 + public boolean containsKey(Object key) {
1.2732 + if (key == null) throw new NullPointerException();
1.2733 + K k = (K)key;
1.2734 + return inBounds(k) && m.containsKey(k);
1.2735 + }
1.2736 +
1.2737 + public V get(Object key) {
1.2738 + if (key == null) throw new NullPointerException();
1.2739 + K k = (K)key;
1.2740 + return ((!inBounds(k)) ? null : m.get(k));
1.2741 + }
1.2742 +
1.2743 + public V put(K key, V value) {
1.2744 + checkKeyBounds(key);
1.2745 + return m.put(key, value);
1.2746 + }
1.2747 +
1.2748 + public V remove(Object key) {
1.2749 + K k = (K)key;
1.2750 + return (!inBounds(k)) ? null : m.remove(k);
1.2751 + }
1.2752 +
1.2753 + public int size() {
1.2754 + long count = 0;
1.2755 + for (ConcurrentSkipListMap.Node<K,V> n = loNode();
1.2756 + isBeforeEnd(n);
1.2757 + n = n.next) {
1.2758 + if (n.getValidValue() != null)
1.2759 + ++count;
1.2760 + }
1.2761 + return count >= Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)count;
1.2762 + }
1.2763 +
1.2764 + public boolean isEmpty() {
1.2765 + return !isBeforeEnd(loNode());
1.2766 + }
1.2767 +
1.2768 + public boolean containsValue(Object value) {
1.2769 + if (value == null)
1.2770 + throw new NullPointerException();
1.2771 + for (ConcurrentSkipListMap.Node<K,V> n = loNode();
1.2772 + isBeforeEnd(n);
1.2773 + n = n.next) {
1.2774 + V v = n.getValidValue();
1.2775 + if (v != null && value.equals(v))
1.2776 + return true;
1.2777 + }
1.2778 + return false;
1.2779 + }
1.2780 +
1.2781 + public void clear() {
1.2782 + for (ConcurrentSkipListMap.Node<K,V> n = loNode();
1.2783 + isBeforeEnd(n);
1.2784 + n = n.next) {
1.2785 + if (n.getValidValue() != null)
1.2786 + m.remove(n.key);
1.2787 + }
1.2788 + }
1.2789 +
1.2790 + /* ---------------- ConcurrentMap API methods -------------- */
1.2791 +
1.2792 + public V putIfAbsent(K key, V value) {
1.2793 + checkKeyBounds(key);
1.2794 + return m.putIfAbsent(key, value);
1.2795 + }
1.2796 +
1.2797 + public boolean remove(Object key, Object value) {
1.2798 + K k = (K)key;
1.2799 + return inBounds(k) && m.remove(k, value);
1.2800 + }
1.2801 +
1.2802 + public boolean replace(K key, V oldValue, V newValue) {
1.2803 + checkKeyBounds(key);
1.2804 + return m.replace(key, oldValue, newValue);
1.2805 + }
1.2806 +
1.2807 + public V replace(K key, V value) {
1.2808 + checkKeyBounds(key);
1.2809 + return m.replace(key, value);
1.2810 + }
1.2811 +
1.2812 + /* ---------------- SortedMap API methods -------------- */
1.2813 +
1.2814 + public Comparator<? super K> comparator() {
1.2815 + Comparator<? super K> cmp = m.comparator();
1.2816 + if (isDescending)
1.2817 + return Collections.reverseOrder(cmp);
1.2818 + else
1.2819 + return cmp;
1.2820 + }
1.2821 +
1.2822 + /**
1.2823 + * Utility to create submaps, where given bounds override
1.2824 + * unbounded(null) ones and/or are checked against bounded ones.
1.2825 + */
1.2826 + private SubMap<K,V> newSubMap(K fromKey,
1.2827 + boolean fromInclusive,
1.2828 + K toKey,
1.2829 + boolean toInclusive) {
1.2830 + if (isDescending) { // flip senses
1.2831 + K tk = fromKey;
1.2832 + fromKey = toKey;
1.2833 + toKey = tk;
1.2834 + boolean ti = fromInclusive;
1.2835 + fromInclusive = toInclusive;
1.2836 + toInclusive = ti;
1.2837 + }
1.2838 + if (lo != null) {
1.2839 + if (fromKey == null) {
1.2840 + fromKey = lo;
1.2841 + fromInclusive = loInclusive;
1.2842 + }
1.2843 + else {
1.2844 + int c = m.compare(fromKey, lo);
1.2845 + if (c < 0 || (c == 0 && !loInclusive && fromInclusive))
1.2846 + throw new IllegalArgumentException("key out of range");
1.2847 + }
1.2848 + }
1.2849 + if (hi != null) {
1.2850 + if (toKey == null) {
1.2851 + toKey = hi;
1.2852 + toInclusive = hiInclusive;
1.2853 + }
1.2854 + else {
1.2855 + int c = m.compare(toKey, hi);
1.2856 + if (c > 0 || (c == 0 && !hiInclusive && toInclusive))
1.2857 + throw new IllegalArgumentException("key out of range");
1.2858 + }
1.2859 + }
1.2860 + return new SubMap<K,V>(m, fromKey, fromInclusive,
1.2861 + toKey, toInclusive, isDescending);
1.2862 + }
1.2863 +
1.2864 + public SubMap<K,V> subMap(K fromKey,
1.2865 + boolean fromInclusive,
1.2866 + K toKey,
1.2867 + boolean toInclusive) {
1.2868 + if (fromKey == null || toKey == null)
1.2869 + throw new NullPointerException();
1.2870 + return newSubMap(fromKey, fromInclusive, toKey, toInclusive);
1.2871 + }
1.2872 +
1.2873 + public SubMap<K,V> headMap(K toKey,
1.2874 + boolean inclusive) {
1.2875 + if (toKey == null)
1.2876 + throw new NullPointerException();
1.2877 + return newSubMap(null, false, toKey, inclusive);
1.2878 + }
1.2879 +
1.2880 + public SubMap<K,V> tailMap(K fromKey,
1.2881 + boolean inclusive) {
1.2882 + if (fromKey == null)
1.2883 + throw new NullPointerException();
1.2884 + return newSubMap(fromKey, inclusive, null, false);
1.2885 + }
1.2886 +
1.2887 + public SubMap<K,V> subMap(K fromKey, K toKey) {
1.2888 + return subMap(fromKey, true, toKey, false);
1.2889 + }
1.2890 +
1.2891 + public SubMap<K,V> headMap(K toKey) {
1.2892 + return headMap(toKey, false);
1.2893 + }
1.2894 +
1.2895 + public SubMap<K,V> tailMap(K fromKey) {
1.2896 + return tailMap(fromKey, true);
1.2897 + }
1.2898 +
1.2899 + public SubMap<K,V> descendingMap() {
1.2900 + return new SubMap<K,V>(m, lo, loInclusive,
1.2901 + hi, hiInclusive, !isDescending);
1.2902 + }
1.2903 +
1.2904 + /* ---------------- Relational methods -------------- */
1.2905 +
1.2906 + public Map.Entry<K,V> ceilingEntry(K key) {
1.2907 + return getNearEntry(key, (m.GT|m.EQ));
1.2908 + }
1.2909 +
1.2910 + public K ceilingKey(K key) {
1.2911 + return getNearKey(key, (m.GT|m.EQ));
1.2912 + }
1.2913 +
1.2914 + public Map.Entry<K,V> lowerEntry(K key) {
1.2915 + return getNearEntry(key, (m.LT));
1.2916 + }
1.2917 +
1.2918 + public K lowerKey(K key) {
1.2919 + return getNearKey(key, (m.LT));
1.2920 + }
1.2921 +
1.2922 + public Map.Entry<K,V> floorEntry(K key) {
1.2923 + return getNearEntry(key, (m.LT|m.EQ));
1.2924 + }
1.2925 +
1.2926 + public K floorKey(K key) {
1.2927 + return getNearKey(key, (m.LT|m.EQ));
1.2928 + }
1.2929 +
1.2930 + public Map.Entry<K,V> higherEntry(K key) {
1.2931 + return getNearEntry(key, (m.GT));
1.2932 + }
1.2933 +
1.2934 + public K higherKey(K key) {
1.2935 + return getNearKey(key, (m.GT));
1.2936 + }
1.2937 +
1.2938 + public K firstKey() {
1.2939 + return isDescending ? highestKey() : lowestKey();
1.2940 + }
1.2941 +
1.2942 + public K lastKey() {
1.2943 + return isDescending ? lowestKey() : highestKey();
1.2944 + }
1.2945 +
1.2946 + public Map.Entry<K,V> firstEntry() {
1.2947 + return isDescending ? highestEntry() : lowestEntry();
1.2948 + }
1.2949 +
1.2950 + public Map.Entry<K,V> lastEntry() {
1.2951 + return isDescending ? lowestEntry() : highestEntry();
1.2952 + }
1.2953 +
1.2954 + public Map.Entry<K,V> pollFirstEntry() {
1.2955 + return isDescending ? removeHighest() : removeLowest();
1.2956 + }
1.2957 +
1.2958 + public Map.Entry<K,V> pollLastEntry() {
1.2959 + return isDescending ? removeLowest() : removeHighest();
1.2960 + }
1.2961 +
1.2962 + /* ---------------- Submap Views -------------- */
1.2963 +
1.2964 + public NavigableSet<K> keySet() {
1.2965 + KeySet<K> ks = keySetView;
1.2966 + return (ks != null) ? ks : (keySetView = new KeySet(this));
1.2967 + }
1.2968 +
1.2969 + public NavigableSet<K> navigableKeySet() {
1.2970 + KeySet<K> ks = keySetView;
1.2971 + return (ks != null) ? ks : (keySetView = new KeySet(this));
1.2972 + }
1.2973 +
1.2974 + public Collection<V> values() {
1.2975 + Collection<V> vs = valuesView;
1.2976 + return (vs != null) ? vs : (valuesView = new Values(this));
1.2977 + }
1.2978 +
1.2979 + public Set<Map.Entry<K,V>> entrySet() {
1.2980 + Set<Map.Entry<K,V>> es = entrySetView;
1.2981 + return (es != null) ? es : (entrySetView = new EntrySet(this));
1.2982 + }
1.2983 +
1.2984 + public NavigableSet<K> descendingKeySet() {
1.2985 + return descendingMap().navigableKeySet();
1.2986 + }
1.2987 +
1.2988 + Iterator<K> keyIterator() {
1.2989 + return new SubMapKeyIterator();
1.2990 + }
1.2991 +
1.2992 + Iterator<V> valueIterator() {
1.2993 + return new SubMapValueIterator();
1.2994 + }
1.2995 +
1.2996 + Iterator<Map.Entry<K,V>> entryIterator() {
1.2997 + return new SubMapEntryIterator();
1.2998 + }
1.2999 +
1.3000 + /**
1.3001 + * Variant of main Iter class to traverse through submaps.
1.3002 + */
1.3003 + abstract class SubMapIter<T> implements Iterator<T> {
1.3004 + /** the last node returned by next() */
1.3005 + Node<K,V> lastReturned;
1.3006 + /** the next node to return from next(); */
1.3007 + Node<K,V> next;
1.3008 + /** Cache of next value field to maintain weak consistency */
1.3009 + V nextValue;
1.3010 +
1.3011 + SubMapIter() {
1.3012 + for (;;) {
1.3013 + next = isDescending ? hiNode() : loNode();
1.3014 + if (next == null)
1.3015 + break;
1.3016 + Object x = next.value;
1.3017 + if (x != null && x != next) {
1.3018 + if (! inBounds(next.key))
1.3019 + next = null;
1.3020 + else
1.3021 + nextValue = (V) x;
1.3022 + break;
1.3023 + }
1.3024 + }
1.3025 + }
1.3026 +
1.3027 + public final boolean hasNext() {
1.3028 + return next != null;
1.3029 + }
1.3030 +
1.3031 + final void advance() {
1.3032 + if (next == null)
1.3033 + throw new NoSuchElementException();
1.3034 + lastReturned = next;
1.3035 + if (isDescending)
1.3036 + descend();
1.3037 + else
1.3038 + ascend();
1.3039 + }
1.3040 +
1.3041 + private void ascend() {
1.3042 + for (;;) {
1.3043 + next = next.next;
1.3044 + if (next == null)
1.3045 + break;
1.3046 + Object x = next.value;
1.3047 + if (x != null && x != next) {
1.3048 + if (tooHigh(next.key))
1.3049 + next = null;
1.3050 + else
1.3051 + nextValue = (V) x;
1.3052 + break;
1.3053 + }
1.3054 + }
1.3055 + }
1.3056 +
1.3057 + private void descend() {
1.3058 + for (;;) {
1.3059 + next = m.findNear(lastReturned.key, LT);
1.3060 + if (next == null)
1.3061 + break;
1.3062 + Object x = next.value;
1.3063 + if (x != null && x != next) {
1.3064 + if (tooLow(next.key))
1.3065 + next = null;
1.3066 + else
1.3067 + nextValue = (V) x;
1.3068 + break;
1.3069 + }
1.3070 + }
1.3071 + }
1.3072 +
1.3073 + public void remove() {
1.3074 + Node<K,V> l = lastReturned;
1.3075 + if (l == null)
1.3076 + throw new IllegalStateException();
1.3077 + m.remove(l.key);
1.3078 + lastReturned = null;
1.3079 + }
1.3080 +
1.3081 + }
1.3082 +
1.3083 + final class SubMapValueIterator extends SubMapIter<V> {
1.3084 + public V next() {
1.3085 + V v = nextValue;
1.3086 + advance();
1.3087 + return v;
1.3088 + }
1.3089 + }
1.3090 +
1.3091 + final class SubMapKeyIterator extends SubMapIter<K> {
1.3092 + public K next() {
1.3093 + Node<K,V> n = next;
1.3094 + advance();
1.3095 + return n.key;
1.3096 + }
1.3097 + }
1.3098 +
1.3099 + final class SubMapEntryIterator extends SubMapIter<Map.Entry<K,V>> {
1.3100 + public Map.Entry<K,V> next() {
1.3101 + Node<K,V> n = next;
1.3102 + V v = nextValue;
1.3103 + advance();
1.3104 + return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
1.3105 + }
1.3106 + }
1.3107 + }
1.3108 +
1.3109 + // Unsafe mechanics
1.3110 + private static final sun.misc.Unsafe UNSAFE;
1.3111 + private static final long headOffset;
1.3112 + static {
1.3113 + try {
1.3114 + UNSAFE = sun.misc.Unsafe.getUnsafe();
1.3115 + Class k = ConcurrentSkipListMap.class;
1.3116 + headOffset = UNSAFE.objectFieldOffset
1.3117 + (k.getDeclaredField("head"));
1.3118 + } catch (Exception e) {
1.3119 + throw new Error(e);
1.3120 + }
1.3121 + }
1.3122 +}