1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
3 *
4 * This code is free software; you can redistribute it and/or modify it
5 * under the terms of the GNU General Public License version 2 only, as
6 * published by the Free Software Foundation. Oracle designates this
7 * particular file as subject to the "Classpath" exception as provided
8 * by Oracle in the LICENSE file that accompanied this code.
9 *
10 * This code is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * version 2 for more details (a copy is included in the LICENSE file that
14 * accompanied this code).
15 *
16 * You should have received a copy of the GNU General Public License version
17 * 2 along with this work; if not, write to the Free Software Foundation,
18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 *
20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 * or visit www.oracle.com if you need additional information or have any
22 * questions.
23 */
24
25 /*
26 * This file is available under and governed by the GNU General Public
27 * License version 2 only, as published by the Free Software Foundation.
28 * However, the following notice accompanied the original version of this
29 * file:
30 *
31 * Written by Doug Lea with assistance from members of JCP JSR-166
32 * Expert Group and released to the public domain, as explained at
33 * http://creativecommons.org/publicdomain/zero/1.0/
34 */
35
36 package java.util.concurrent;
37
38 import java.lang.invoke.MethodHandles;
39 import java.lang.invoke.VarHandle;
40 import java.io.Serializable;
41 import java.util.AbstractCollection;
42 import java.util.AbstractMap;
43 import java.util.AbstractSet;
44 import java.util.ArrayList;
45 import java.util.Collection;
46 import java.util.Collections;
47 import java.util.Comparator;
48 import java.util.Iterator;
49 import java.util.List;
50 import java.util.Map;
51 import java.util.NavigableSet;
52 import java.util.NoSuchElementException;
53 import java.util.Set;
54 import java.util.SortedMap;
55 import java.util.Spliterator;
56 import java.util.function.BiConsumer;
57 import java.util.function.BiFunction;
58 import java.util.function.Consumer;
59 import java.util.function.Function;
60 import java.util.function.Predicate;
61 import java.util.concurrent.atomic.LongAdder;
62
63 /**
64 * A scalable concurrent {@link ConcurrentNavigableMap} implementation.
65 * The map is sorted according to the {@linkplain Comparable natural
66 * ordering} of its keys, or by a {@link Comparator} provided at map
67 * creation time, depending on which constructor is used.
68 *
69 * <p>This class implements a concurrent variant of <a
70 * href="http://en.wikipedia.org/wiki/Skip_list" target="_top">SkipLists</a>
71 * providing expected average <i>log(n)</i> time cost for the
72 * {@code containsKey}, {@code get}, {@code put} and
73 * {@code remove} operations and their variants. Insertion, removal,
74 * update, and access operations safely execute concurrently by
75 * multiple threads.
76 *
77 * <p>Iterators and spliterators are
78 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
79 *
80 * <p>Ascending key ordered views and their iterators are faster than
81 * descending ones.
82 *
83 * <p>All {@code Map.Entry} pairs returned by methods in this class
84 * and its views represent snapshots of mappings at the time they were
85 * produced. They do <em>not</em> support the {@code Entry.setValue}
86 * method. (Note however that it is possible to change mappings in the
87 * associated map using {@code put}, {@code putIfAbsent}, or
88 * {@code replace}, depending on exactly which effect you need.)
89 *
90 * <p>Beware that bulk operations {@code putAll}, {@code equals},
91 * {@code toArray}, {@code containsValue}, and {@code clear} are
92 * <em>not</em> guaranteed to be performed atomically. For example, an
93 * iterator operating concurrently with a {@code putAll} operation
94 * might view only some of the added elements.
95 *
96 * <p>This class and its views and iterators implement all of the
97 * <em>optional</em> methods of the {@link Map} and {@link Iterator}
98 * interfaces. Like most other concurrent collections, this class does
99 * <em>not</em> permit the use of {@code null} keys or values because some
100 * null return values cannot be reliably distinguished from the absence of
101 * elements.
102 *
103 * <p>This class is a member of the
104 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
105 * Java Collections Framework</a>.
106 *
107 * @author Doug Lea
108 * @param <K> the type of keys maintained by this map
109 * @param <V> the type of mapped values
110 * @since 1.6
111 */
112 public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
113 implements ConcurrentNavigableMap<K,V>, Cloneable, Serializable {
114 /*
115 * This class implements a tree-like two-dimensionally linked skip
116 * list in which the index levels are represented in separate
117 * nodes from the base nodes holding data. There are two reasons
118 * for taking this approach instead of the usual array-based
119 * structure: 1) Array based implementations seem to encounter
120 * more complexity and overhead 2) We can use cheaper algorithms
121 * for the heavily-traversed index lists than can be used for the
122 * base lists. Here's a picture of some of the basics for a
123 * possible list with 2 levels of index:
124 *
125 * Head nodes Index nodes
126 * +-+ right +-+ +-+
127 * |2|---------------->| |--------------------->| |->null
128 * +-+ +-+ +-+
129 * | down | |
130 * v v v
131 * +-+ +-+ +-+ +-+ +-+ +-+
132 * |1|----------->| |->| |------>| |----------->| |------>| |->null
133 * +-+ +-+ +-+ +-+ +-+ +-+
134 * v | | | | |
135 * Nodes next v v v v v
136 * +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
137 * | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null
138 * +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
139 *
140 * The base lists use a variant of the HM linked ordered set
141 * algorithm. See Tim Harris, "A pragmatic implementation of
142 * non-blocking linked lists"
143 * http://www.cl.cam.ac.uk/~tlh20/publications.html and Maged
144 * Michael "High Performance Dynamic Lock-Free Hash Tables and
145 * List-Based Sets"
146 * http://www.research.ibm.com/people/m/michael/pubs.htm. The
147 * basic idea in these lists is to mark the "next" pointers of
148 * deleted nodes when deleting to avoid conflicts with concurrent
149 * insertions, and when traversing to keep track of triples
150 * (predecessor, node, successor) in order to detect when and how
151 * to unlink these deleted nodes.
152 *
153 * Rather than using mark-bits to mark list deletions (which can
154 * be slow and space-intensive using AtomicMarkedReference), nodes
155 * use direct CAS'able next pointers. On deletion, instead of
156 * marking a pointer, they splice in another node that can be
157 * thought of as standing for a marked pointer (see method
158 * unlinkNode). Using plain nodes acts roughly like "boxed"
159 * implementations of marked pointers, but uses new nodes only
160 * when nodes are deleted, not for every link. This requires less
161 * space and supports faster traversal. Even if marked references
162 * were better supported by JVMs, traversal using this technique
163 * might still be faster because any search need only read ahead
164 * one more node than otherwise required (to check for trailing
165 * marker) rather than unmasking mark bits or whatever on each
166 * read.
167 *
168 * This approach maintains the essential property needed in the HM
169 * algorithm of changing the next-pointer of a deleted node so
170 * that any other CAS of it will fail, but implements the idea by
171 * changing the pointer to point to a different node (with
172 * otherwise illegal null fields), not by marking it. While it
173 * would be possible to further squeeze space by defining marker
174 * nodes not to have key/value fields, it isn't worth the extra
175 * type-testing overhead. The deletion markers are rarely
176 * encountered during traversal, are easily detected via null
177 * checks that are needed anyway, and are normally quickly garbage
178 * collected. (Note that this technique would not work well in
179 * systems without garbage collection.)
180 *
181 * In addition to using deletion markers, the lists also use
182 * nullness of value fields to indicate deletion, in a style
183 * similar to typical lazy-deletion schemes. If a node's value is
184 * null, then it is considered logically deleted and ignored even
185 * though it is still reachable.
186 *
187 * Here's the sequence of events for a deletion of node n with
188 * predecessor b and successor f, initially:
189 *
190 * +------+ +------+ +------+
191 * ... | b |------>| n |----->| f | ...
192 * +------+ +------+ +------+
193 *
194 * 1. CAS n's value field from non-null to null.
195 * Traversals encountering a node with null value ignore it.
196 * However, ongoing insertions and deletions might still modify
197 * n's next pointer.
198 *
199 * 2. CAS n's next pointer to point to a new marker node.
200 * From this point on, no other nodes can be appended to n.
201 * which avoids deletion errors in CAS-based linked lists.
202 *
203 * +------+ +------+ +------+ +------+
204 * ... | b |------>| n |----->|marker|------>| f | ...
205 * +------+ +------+ +------+ +------+
206 *
207 * 3. CAS b's next pointer over both n and its marker.
208 * From this point on, no new traversals will encounter n,
209 * and it can eventually be GCed.
210 * +------+ +------+
211 * ... | b |----------------------------------->| f | ...
212 * +------+ +------+
213 *
214 * A failure at step 1 leads to simple retry due to a lost race
215 * with another operation. Steps 2-3 can fail because some other
216 * thread noticed during a traversal a node with null value and
217 * helped out by marking and/or unlinking. This helping-out
218 * ensures that no thread can become stuck waiting for progress of
219 * the deleting thread.
220 *
221 * Skip lists add indexing to this scheme, so that the base-level
222 * traversals start close to the locations being found, inserted
223 * or deleted -- usually base level traversals only traverse a few
224 * nodes. This doesn't change the basic algorithm except for the
225 * need to make sure base traversals start at predecessors (here,
226 * b) that are not (structurally) deleted, otherwise retrying
227 * after processing the deletion.
228 *
229 * Index levels are maintained using CAS to link and unlink
230 * successors ("right" fields). Races are allowed in index-list
231 * operations that can (rarely) fail to link in a new index node.
232 * (We can't do this of course for data nodes.) However, even
233 * when this happens, the index lists correctly guide search.
234 * This can impact performance, but since skip lists are
235 * probabilistic anyway, the net result is that under contention,
236 * the effective "p" value may be lower than its nominal value.
237 *
238 * Index insertion and deletion sometimes require a separate
239 * traversal pass occurring after the base-level action, to add or
240 * remove index nodes. This adds to single-threaded overhead, but
241 * improves contended multithreaded performance by narrowing
242 * interference windows, and allows deletion to ensure that all
243 * index nodes will be made unreachable upon return from a public
244 * remove operation, thus avoiding unwanted garbage retention.
245 *
246 * Indexing uses skip list parameters that maintain good search
247 * performance while using sparser-than-usual indices: The
248 * hardwired parameters k=1, p=0.5 (see method doPut) mean that
249 * about one-quarter of the nodes have indices. Of those that do,
250 * half have one level, a quarter have two, and so on (see Pugh's
251 * Skip List Cookbook, sec 3.4), up to a maximum of 62 levels
252 * (appropriate for up to 2^63 elements). The expected total
253 * space requirement for a map is slightly less than for the
254 * current implementation of java.util.TreeMap.
255 *
256 * Changing the level of the index (i.e, the height of the
257 * tree-like structure) also uses CAS. Creation of an index with
258 * height greater than the current level adds a level to the head
259 * index by CAS'ing on a new top-most head. To maintain good
260 * performance after a lot of removals, deletion methods
261 * heuristically try to reduce the height if the topmost levels
262 * appear to be empty. This may encounter races in which it is
263 * possible (but rare) to reduce and "lose" a level just as it is
264 * about to contain an index (that will then never be
265 * encountered). This does no structural harm, and in practice
266 * appears to be a better option than allowing unrestrained growth
267 * of levels.
268 *
269 * This class provides concurrent-reader-style memory consistency,
270 * ensuring that read-only methods report status and/or values no
271 * staler than those holding at method entry. This is done by
272 * performing all publication and structural updates using
273 * (volatile) CAS, placing an acquireFence in a few access
274 * methods, and ensuring that linked objects are transitively
275 * acquired via dependent reads (normally once) unless performing
276 * a volatile-mode CAS operation (that also acts as an acquire and
277 * release). This form of fence-hoisting is similar to RCU and
278 * related techniques (see McKenney's online book
279 * https://www.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html)
280 * It minimizes overhead that may otherwise occur when using so
281 * many volatile-mode reads. Using explicit acquireFences is
282 * logistically easier than targeting particular fields to be read
283 * in acquire mode: fences are just hoisted up as far as possible,
284 * to the entry points or loop headers of a few methods. A
285 * potential disadvantage is that these few remaining fences are
286 * not easily optimized away by compilers under exclusively
287 * single-thread use. It requires some care to avoid volatile
288 * mode reads of other fields. (Note that the memory semantics of
289 * a reference dependently read in plain mode exactly once are
290 * equivalent to those for atomic opaque mode.) Iterators and
291 * other traversals encounter each node and value exactly once.
292 * Other operations locate an element (or position to insert an
293 * element) via a sequence of dereferences. This search is broken
294 * into two parts. Method findPredecessor (and its specialized
295 * embeddings) searches index nodes only, returning a base-level
296 * predecessor of the key. Callers carry out the base-level
297 * search, restarting if encountering a marker preventing link
298 * modification. In some cases, it is possible to encounter a
299 * node multiple times while descending levels. For mutative
300 * operations, the reported value is validated using CAS (else
301 * retrying), preserving linearizability with respect to each
302 * other. Others may return any (non-null) value holding in the
303 * course of the method call. (Search-based methods also include
304 * some useless-looking explicit null checks designed to allow
305 * more fields to be nulled out upon removal, to reduce floating
306 * garbage, but which is not currently done, pending discovery of
307 * a way to do this with less impact on other operations.)
308 *
309 * To produce random values without interference across threads,
310 * we use within-JDK thread local random support (via the
311 * "secondary seed", to avoid interference with user-level
312 * ThreadLocalRandom.)
313 *
314 * For explanation of algorithms sharing at least a couple of
315 * features with this one, see Mikhail Fomitchev's thesis
316 * (http://www.cs.yorku.ca/~mikhail/), Keir Fraser's thesis
317 * (http://www.cl.cam.ac.uk/users/kaf24/), and Hakan Sundell's
318 * thesis (http://www.cs.chalmers.se/~phs/).
319 *
320 * Notation guide for local variables
321 * Node: b, n, f, p for predecessor, node, successor, aux
322 * Index: q, r, d for index node, right, down.
323 * Head: h
324 * Keys: k, key
325 * Values: v, value
326 * Comparisons: c
327 */
328
329 private static final long serialVersionUID = -8627078645895051609L;
330
331 /**
332 * The comparator used to maintain order in this map, or null if
333 * using natural ordering. (Non-private to simplify access in
334 * nested classes.)
335 * @serial
336 */
337 final Comparator<? super K> comparator;
338
339 /** Lazily initialized topmost index of the skiplist. */
340 private transient Index<K,V> head;
341 /** Lazily initialized element count */
342 private transient LongAdder adder;
343 /** Lazily initialized key set */
344 private transient KeySet<K,V> keySet;
345 /** Lazily initialized values collection */
346 private transient Values<K,V> values;
347 /** Lazily initialized entry set */
348 private transient EntrySet<K,V> entrySet;
349 /** Lazily initialized descending map */
350 private transient SubMap<K,V> descendingMap;
351
352 /**
353 * Nodes hold keys and values, and are singly linked in sorted
354 * order, possibly with some intervening marker nodes. The list is
355 * headed by a header node accessible as head.node. Headers and
356 * marker nodes have null keys. The val field (but currently not
357 * the key field) is nulled out upon deletion.
358 */
359 static final class Node<K,V> {
360 final K key; // currently, never detached
361 V val;
362 Node<K,V> next;
363 Node(K key, V value, Node<K,V> next) {
364 this.key = key;
365 this.val = value;
366 this.next = next;
367 }
368 }
369
370 /**
371 * Index nodes represent the levels of the skip list.
372 */
373 static final class Index<K,V> {
374 final Node<K,V> node; // currently, never detached
375 final Index<K,V> down;
376 Index<K,V> right;
377 Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
378 this.node = node;
379 this.down = down;
380 this.right = right;
381 }
382 }
383
384 /* ---------------- Utilities -------------- */
385
386 /**
387 * Compares using comparator or natural ordering if null.
388 * Called only by methods that have performed required type checks.
389 */
390 @SuppressWarnings({"unchecked", "rawtypes"})
391 static int cpr(Comparator c, Object x, Object y) {
392 return (c != null) ? c.compare(x, y) : ((Comparable)x).compareTo(y);
393 }
394
395 /**
396 * Returns the header for base node list, or null if uninitialized
397 */
398 final Node<K,V> baseHead() {
399 Index<K,V> h;
400 VarHandle.acquireFence();
401 return ((h = head) == null) ? null : h.node;
402 }
403
404 /**
405 * Tries to unlink deleted node n from predecessor b (if both
406 * exist), by first splicing in a marker if not already present.
407 * Upon return, node n is sure to be unlinked from b, possibly
408 * via the actions of some other thread.
409 *
410 * @param b if nonnull, predecessor
411 * @param n if nonnull, node known to be deleted
412 */
413 static <K,V> void unlinkNode(Node<K,V> b, Node<K,V> n) {
414 if (b != null && n != null) {
415 Node<K,V> f, p;
416 for (;;) {
417 if ((f = n.next) != null && f.key == null) {
418 p = f.next; // already marked
419 break;
420 }
421 else if (NEXT.compareAndSet(n, f,
422 new Node<K,V>(null, null, f))) {
423 p = f; // add marker
424 break;
425 }
426 }
427 NEXT.compareAndSet(b, n, p);
428 }
429 }
430
431 /**
432 * Adds to element count, initializing adder if necessary
433 *
434 * @param c count to add
435 */
436 private void addCount(long c) {
437 LongAdder a;
438 do {} while ((a = adder) == null &&
439 !ADDER.compareAndSet(this, null, a = new LongAdder()));
440 a.add(c);
441 }
442
443 /**
444 * Returns element count, initializing adder if necessary.
445 */
446 final long getAdderCount() {
447 LongAdder a; long c;
448 do {} while ((a = adder) == null &&
449 !ADDER.compareAndSet(this, null, a = new LongAdder()));
450 return ((c = a.sum()) <= 0L) ? 0L : c; // ignore transient negatives
451 }
452
453 /* ---------------- Traversal -------------- */
454
455 /**
456 * Returns an index node with key strictly less than given key.
457 * Also unlinks indexes to deleted nodes found along the way.
458 * Callers rely on this side-effect of clearing indices to deleted
459 * nodes.
460 *
461 * @param key if nonnull the key
462 * @return a predecessor node of key, or null if uninitialized or null key
463 */
464 private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {
465 Index<K,V> q;
466 VarHandle.acquireFence();
467 if ((q = head) == null || key == null)
468 return null;
469 else {
470 for (Index<K,V> r, d;;) {
471 while ((r = q.right) != null) {
472 Node<K,V> p; K k;
473 if ((p = r.node) == null || (k = p.key) == null ||
474 p.val == null) // unlink index to deleted node
475 RIGHT.compareAndSet(q, r, r.right);
476 else if (cpr(cmp, key, k) > 0)
477 q = r;
478 else
479 break;
480 }
481 if ((d = q.down) != null)
482 q = d;
483 else
484 return q.node;
485 }
486 }
487 }
488
489 /**
490 * Returns node holding key or null if no such, clearing out any
491 * deleted nodes seen along the way. Repeatedly traverses at
492 * base-level looking for key starting at predecessor returned
493 * from findPredecessor, processing base-level deletions as
494 * encountered. Restarts occur, at traversal step encountering
495 * node n, if n's key field is null, indicating it is a marker, so
496 * its predecessor is deleted before continuing, which we help do
497 * by re-finding a valid predecessor. The traversal loops in
498 * doPut, doRemove, and findNear all include the same checks.
499 *
500 * @param key the key
501 * @return node holding key, or null if no such
502 */
503 private Node<K,V> findNode(Object key) {
504 if (key == null)
505 throw new NullPointerException(); // don't postpone errors
506 Comparator<? super K> cmp = comparator;
507 Node<K,V> b;
508 outer: while ((b = findPredecessor(key, cmp)) != null) {
509 for (;;) {
510 Node<K,V> n; K k; V v; int c;
511 if ((n = b.next) == null)
512 break outer; // empty
513 else if ((k = n.key) == null)
514 break; // b is deleted
515 else if ((v = n.val) == null)
516 unlinkNode(b, n); // n is deleted
517 else if ((c = cpr(cmp, key, k)) > 0)
518 b = n;
519 else if (c == 0)
520 return n;
521 else
522 break outer;
523 }
524 }
525 return null;
526 }
527
528 /**
529 * Gets value for key. Same idea as findNode, except skips over
530 * deletions and markers, and returns first encountered value to
531 * avoid possibly inconsistent rereads.
532 *
533 * @param key the key
534 * @return the value, or null if absent
535 */
536 private V doGet(Object key) {
537 Index<K,V> q;
538 VarHandle.acquireFence();
539 if (key == null)
540 throw new NullPointerException();
541 Comparator<? super K> cmp = comparator;
542 V result = null;
543 if ((q = head) != null) {
544 outer: for (Index<K,V> r, d;;) {
545 while ((r = q.right) != null) {
546 Node<K,V> p; K k; V v; int c;
547 if ((p = r.node) == null || (k = p.key) == null ||
548 (v = p.val) == null)
549 RIGHT.compareAndSet(q, r, r.right);
550 else if ((c = cpr(cmp, key, k)) > 0)
551 q = r;
552 else if (c == 0) {
553 result = v;
554 break outer;
555 }
556 else
557 break;
558 }
559 if ((d = q.down) != null)
560 q = d;
561 else {
562 Node<K,V> b, n;
563 if ((b = q.node) != null) {
564 while ((n = b.next) != null) {
565 V v; int c;
566 K k = n.key;
567 if ((v = n.val) == null || k == null ||
568 (c = cpr(cmp, key, k)) > 0)
569 b = n;
570 else {
571 if (c == 0)
572 result = v;
573 break;
574 }
575 }
576 }
577 break;
578 }
579 }
580 }
581 return result;
582 }
583
584 /* ---------------- Insertion -------------- */
585
586 /**
587 * Main insertion method. Adds element if not present, or
588 * replaces value if present and onlyIfAbsent is false.
589 *
590 * @param key the key
591 * @param value the value that must be associated with key
592 * @param onlyIfAbsent if should not insert if already present
593 * @return the old value, or null if newly inserted
594 */
595 private V doPut(K key, V value, boolean onlyIfAbsent) {
596 if (key == null)
597 throw new NullPointerException();
598 Comparator<? super K> cmp = comparator;
599 for (;;) {
600 Index<K,V> h; Node<K,V> b;
601 VarHandle.acquireFence();
602 int levels = 0; // number of levels descended
603 if ((h = head) == null) { // try to initialize
604 Node<K,V> base = new Node<K,V>(null, null, null);
605 h = new Index<K,V>(base, null, null);
606 b = (HEAD.compareAndSet(this, null, h)) ? base : null;
607 }
608 else {
609 for (Index<K,V> q = h, r, d;;) { // count while descending
610 while ((r = q.right) != null) {
611 Node<K,V> p; K k;
612 if ((p = r.node) == null || (k = p.key) == null ||
613 p.val == null)
614 RIGHT.compareAndSet(q, r, r.right);
615 else if (cpr(cmp, key, k) > 0)
616 q = r;
617 else
618 break;
619 }
620 if ((d = q.down) != null) {
621 ++levels;
622 q = d;
623 }
624 else {
625 b = q.node;
626 break;
627 }
628 }
629 }
630 if (b != null) {
631 Node<K,V> z = null; // new node, if inserted
632 for (;;) { // find insertion point
633 Node<K,V> n, p; K k; V v; int c;
634 if ((n = b.next) == null) {
635 if (b.key == null) // if empty, type check key now
636 cpr(cmp, key, key);
637 c = -1;
638 }
639 else if ((k = n.key) == null)
640 break; // can't append; restart
641 else if ((v = n.val) == null) {
642 unlinkNode(b, n);
643 c = 1;
644 }
645 else if ((c = cpr(cmp, key, k)) > 0)
646 b = n;
647 else if (c == 0 &&
648 (onlyIfAbsent || VAL.compareAndSet(n, v, value)))
649 return v;
650
651 if (c < 0 &&
652 NEXT.compareAndSet(b, n,
653 p = new Node<K,V>(key, value, n))) {
654 z = p;
655 break;
656 }
657 }
658
659 if (z != null) {
660 int lr = ThreadLocalRandom.nextSecondarySeed();
661 if ((lr & 0x3) == 0) { // add indices with 1/4 prob
662 int hr = ThreadLocalRandom.nextSecondarySeed();
663 long rnd = ((long)hr << 32) | ((long)lr & 0xffffffffL);
664 int skips = levels; // levels to descend before add
665 Index<K,V> x = null;
666 for (;;) { // create at most 62 indices
667 x = new Index<K,V>(z, x, null);
668 if (rnd >= 0L || --skips < 0)
669 break;
670 else
671 rnd <<= 1;
672 }
673 if (addIndices(h, skips, x, cmp) && skips < 0 &&
674 head == h) { // try to add new level
675 Index<K,V> hx = new Index<K,V>(z, x, null);
676 Index<K,V> nh = new Index<K,V>(h.node, h, hx);
677 HEAD.compareAndSet(this, h, nh);
678 }
679 if (z.val == null) // deleted while adding indices
680 findPredecessor(key, cmp); // clean
681 }
682 addCount(1L);
683 return null;
684 }
685 }
686 }
687 }
688
689 /**
690 * Add indices after an insertion. Descends iteratively to the
691 * highest level of insertion, then recursively, to chain index
692 * nodes to lower ones. Returns null on (staleness) failure,
693 * disabling higher-level insertions. Recursion depths are
694 * exponentially less probable.
695 *
696 * @param q starting index for current level
697 * @param skips levels to skip before inserting
698 * @param x index for this insertion
699 * @param cmp comparator
700 */
701 static <K,V> boolean addIndices(Index<K,V> q, int skips, Index<K,V> x,
702 Comparator<? super K> cmp) {
703 Node<K,V> z; K key;
704 if (x != null && (z = x.node) != null && (key = z.key) != null &&
705 q != null) { // hoist checks
706 boolean retrying = false;
707 for (;;) { // find splice point
708 Index<K,V> r, d; int c;
709 if ((r = q.right) != null) {
710 Node<K,V> p; K k;
711 if ((p = r.node) == null || (k = p.key) == null ||
712 p.val == null) {
713 RIGHT.compareAndSet(q, r, r.right);
714 c = 0;
715 }
716 else if ((c = cpr(cmp, key, k)) > 0)
717 q = r;
718 else if (c == 0)
719 break; // stale
720 }
721 else
722 c = -1;
723
724 if (c < 0) {
725 if ((d = q.down) != null && skips > 0) {
726 --skips;
727 q = d;
728 }
729 else if (d != null && !retrying &&
730 !addIndices(d, 0, x.down, cmp))
731 break;
732 else {
733 x.right = r;
734 if (RIGHT.compareAndSet(q, r, x))
735 return true;
736 else
737 retrying = true; // re-find splice point
738 }
739 }
740 }
741 }
742 return false;
743 }
744
745 /* ---------------- Deletion -------------- */
746
747 /**
748 * Main deletion method. Locates node, nulls value, appends a
749 * deletion marker, unlinks predecessor, removes associated index
750 * nodes, and possibly reduces head index level.
751 *
752 * @param key the key
753 * @param value if non-null, the value that must be
754 * associated with key
755 * @return the node, or null if not found
756 */
757 final V doRemove(Object key, Object value) {
758 if (key == null)
759 throw new NullPointerException();
760 Comparator<? super K> cmp = comparator;
761 V result = null;
762 Node<K,V> b;
763 outer: while ((b = findPredecessor(key, cmp)) != null &&
764 result == null) {
765 for (;;) {
766 Node<K,V> n; K k; V v; int c;
767 if ((n = b.next) == null)
768 break outer;
769 else if ((k = n.key) == null)
770 break;
771 else if ((v = n.val) == null)
772 unlinkNode(b, n);
773 else if ((c = cpr(cmp, key, k)) > 0)
774 b = n;
775 else if (c < 0)
776 break outer;
777 else if (value != null && !value.equals(v))
778 break outer;
779 else if (VAL.compareAndSet(n, v, null)) {
780 result = v;
781 unlinkNode(b, n);
782 break; // loop to clean up
783 }
784 }
785 }
786 if (result != null) {
787 tryReduceLevel();
788 addCount(-1L);
789 }
790 return result;
791 }
792
793 /**
794 * Possibly reduce head level if it has no nodes. This method can
795 * (rarely) make mistakes, in which case levels can disappear even
796 * though they are about to contain index nodes. This impacts
797 * performance, not correctness. To minimize mistakes as well as
798 * to reduce hysteresis, the level is reduced by one only if the
799 * topmost three levels look empty. Also, if the removed level
800 * looks non-empty after CAS, we try to change it back quick
801 * before anyone notices our mistake! (This trick works pretty
802 * well because this method will practically never make mistakes
803 * unless current thread stalls immediately before first CAS, in
804 * which case it is very unlikely to stall again immediately
805 * afterwards, so will recover.)
806 *
807 * We put up with all this rather than just let levels grow
808 * because otherwise, even a small map that has undergone a large
809 * number of insertions and removals will have a lot of levels,
810 * slowing down access more than would an occasional unwanted
811 * reduction.
812 */
813 private void tryReduceLevel() {
814 Index<K,V> h, d, e;
815 if ((h = head) != null && h.right == null &&
816 (d = h.down) != null && d.right == null &&
817 (e = d.down) != null && e.right == null &&
818 HEAD.compareAndSet(this, h, d) &&
819 h.right != null) // recheck
820 HEAD.compareAndSet(this, d, h); // try to backout
821 }
822
823 /* ---------------- Finding and removing first element -------------- */
824
825 /**
826 * Gets first valid node, unlinking deleted nodes if encountered.
827 * @return first node or null if empty
828 */
829 final Node<K,V> findFirst() {
830 Node<K,V> b, n;
831 if ((b = baseHead()) != null) {
832 while ((n = b.next) != null) {
833 if (n.val == null)
834 unlinkNode(b, n);
835 else
836 return n;
837 }
838 }
839 return null;
840 }
841
842 /**
843 * Entry snapshot version of findFirst
844 */
845 final AbstractMap.SimpleImmutableEntry<K,V> findFirstEntry() {
846 Node<K,V> b, n; V v;
847 if ((b = baseHead()) != null) {
848 while ((n = b.next) != null) {
849 if ((v = n.val) == null)
850 unlinkNode(b, n);
851 else
852 return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
853 }
854 }
855 return null;
856 }
857
858 /**
859 * Removes first entry; returns its snapshot.
860 * @return null if empty, else snapshot of first entry
861 */
862 private AbstractMap.SimpleImmutableEntry<K,V> doRemoveFirstEntry() {
863 Node<K,V> b, n; V v;
864 if ((b = baseHead()) != null) {
865 while ((n = b.next) != null) {
866 if ((v = n.val) == null || VAL.compareAndSet(n, v, null)) {
867 K k = n.key;
868 unlinkNode(b, n);
869 if (v != null) {
870 tryReduceLevel();
871 findPredecessor(k, comparator); // clean index
872 addCount(-1L);
873 return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
874 }
875 }
876 }
877 }
878 return null;
879 }
880
881 /* ---------------- Finding and removing last element -------------- */
882
883 /**
884 * Specialized version of find to get last valid node.
885 * @return last node or null if empty
886 */
887 final Node<K,V> findLast() {
888 outer: for (;;) {
889 Index<K,V> q; Node<K,V> b;
890 VarHandle.acquireFence();
891 if ((q = head) == null)
892 break;
893 for (Index<K,V> r, d;;) {
894 while ((r = q.right) != null) {
895 Node<K,V> p;
896 if ((p = r.node) == null || p.val == null)
897 RIGHT.compareAndSet(q, r, r.right);
898 else
899 q = r;
900 }
901 if ((d = q.down) != null)
902 q = d;
903 else {
904 b = q.node;
905 break;
906 }
907 }
908 if (b != null) {
909 for (;;) {
910 Node<K,V> n;
911 if ((n = b.next) == null) {
912 if (b.key == null) // empty
913 break outer;
914 else
915 return b;
916 }
917 else if (n.key == null)
918 break;
919 else if (n.val == null)
920 unlinkNode(b, n);
921 else
922 b = n;
923 }
924 }
925 }
926 return null;
927 }
928
929 /**
930 * Entry version of findLast
931 * @return Entry for last node or null if empty
932 */
933 final AbstractMap.SimpleImmutableEntry<K,V> findLastEntry() {
934 for (;;) {
935 Node<K,V> n; V v;
936 if ((n = findLast()) == null)
937 return null;
938 if ((v = n.val) != null)
939 return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
940 }
941 }
942
943 /**
944 * Removes last entry; returns its snapshot.
945 * Specialized variant of doRemove.
946 * @return null if empty, else snapshot of last entry
947 */
948 private Map.Entry<K,V> doRemoveLastEntry() {
949 outer: for (;;) {
950 Index<K,V> q; Node<K,V> b;
951 VarHandle.acquireFence();
952 if ((q = head) == null)
953 break;
954 for (;;) {
955 Index<K,V> d, r; Node<K,V> p;
956 while ((r = q.right) != null) {
957 if ((p = r.node) == null || p.val == null)
958 RIGHT.compareAndSet(q, r, r.right);
959 else if (p.next != null)
960 q = r; // continue only if a successor
961 else
962 break;
963 }
964 if ((d = q.down) != null)
965 q = d;
966 else {
967 b = q.node;
968 break;
969 }
970 }
971 if (b != null) {
972 for (;;) {
973 Node<K,V> n; K k; V v;
974 if ((n = b.next) == null) {
975 if (b.key == null) // empty
976 break outer;
977 else
978 break; // retry
979 }
980 else if ((k = n.key) == null)
981 break;
982 else if ((v = n.val) == null)
983 unlinkNode(b, n);
984 else if (n.next != null)
985 b = n;
986 else if (VAL.compareAndSet(n, v, null)) {
987 unlinkNode(b, n);
988 tryReduceLevel();
989 findPredecessor(k, comparator); // clean index
990 addCount(-1L);
991 return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
992 }
993 }
994 }
995 }
996 return null;
997 }
998
999 /* ---------------- Relational operations -------------- */
1000
1001 // Control values OR'ed as arguments to findNear
1002
1003 private static final int EQ = 1;
1004 private static final int LT = 2;
1005 private static final int GT = 0; // Actually checked as !LT
1006
1007 /**
1008 * Utility for ceiling, floor, lower, higher methods.
1009 * @param key the key
1010 * @param rel the relation -- OR'ed combination of EQ, LT, GT
1011 * @return nearest node fitting relation, or null if no such
1012 */
1013 final Node<K,V> findNear(K key, int rel, Comparator<? super K> cmp) {
1014 if (key == null)
1015 throw new NullPointerException();
1016 Node<K,V> result;
1017 outer: for (Node<K,V> b;;) {
1018 if ((b = findPredecessor(key, cmp)) == null) {
1019 result = null;
1020 break; // empty
1021 }
1022 for (;;) {
1023 Node<K,V> n; K k; int c;
1024 if ((n = b.next) == null) {
1025 result = ((rel & LT) != 0 && b.key != null) ? b : null;
1026 break outer;
1027 }
1028 else if ((k = n.key) == null)
1029 break;
1030 else if (n.val == null)
1031 unlinkNode(b, n);
1032 else if (((c = cpr(cmp, key, k)) == 0 && (rel & EQ) != 0) ||
1033 (c < 0 && (rel & LT) == 0)) {
1034 result = n;
1035 break outer;
1036 }
1037 else if (c <= 0 && (rel & LT) != 0) {
1038 result = (b.key != null) ? b : null;
1039 break outer;
1040 }
1041 else
1042 b = n;
1043 }
1044 }
1045 return result;
1046 }
1047
1048 /**
1049 * Variant of findNear returning SimpleImmutableEntry
1050 * @param key the key
1051 * @param rel the relation -- OR'ed combination of EQ, LT, GT
1052 * @return Entry fitting relation, or null if no such
1053 */
1054 final AbstractMap.SimpleImmutableEntry<K,V> findNearEntry(K key, int rel,
1055 Comparator<? super K> cmp) {
1056 for (;;) {
1057 Node<K,V> n; V v;
1058 if ((n = findNear(key, rel, cmp)) == null)
1059 return null;
1060 if ((v = n.val) != null)
1061 return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
1062 }
1063 }
1064
1065 /* ---------------- Constructors -------------- */
1066
1067 /**
1068 * Constructs a new, empty map, sorted according to the
1069 * {@linkplain Comparable natural ordering} of the keys.
1070 */
1071 public ConcurrentSkipListMap() {
1072 this.comparator = null;
1073 }
1074
1075 /**
1076 * Constructs a new, empty map, sorted according to the specified
1077 * comparator.
1078 *
1079 * @param comparator the comparator that will be used to order this map.
1080 * If {@code null}, the {@linkplain Comparable natural
1081 * ordering} of the keys will be used.
1082 */
1083 public ConcurrentSkipListMap(Comparator<? super K> comparator) {
1084 this.comparator = comparator;
1085 }
1086
1087 /**
1088 * Constructs a new map containing the same mappings as the given map,
1089 * sorted according to the {@linkplain Comparable natural ordering} of
1090 * the keys.
1091 *
1092 * @param m the map whose mappings are to be placed in this map
1093 * @throws ClassCastException if the keys in {@code m} are not
1094 * {@link Comparable}, or are not mutually comparable
1095 * @throws NullPointerException if the specified map or any of its keys
1096 * or values are null
1097 */
1098 public ConcurrentSkipListMap(Map<? extends K, ? extends V> m) {
1099 this.comparator = null;
1100 putAll(m);
1101 }
1102
1103 /**
1104 * Constructs a new map containing the same mappings and using the
1105 * same ordering as the specified sorted map.
1106 *
1107 * @param m the sorted map whose mappings are to be placed in this
1108 * map, and whose comparator is to be used to sort this map
1109 * @throws NullPointerException if the specified sorted map or any of
1110 * its keys or values are null
1111 */
1112 public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) {
1113 this.comparator = m.comparator();
1114 buildFromSorted(m); // initializes transients
1115 }
1116
1117 /**
1118 * Returns a shallow copy of this {@code ConcurrentSkipListMap}
1119 * instance. (The keys and values themselves are not cloned.)
1120 *
1121 * @return a shallow copy of this map
1122 */
1123 public ConcurrentSkipListMap<K,V> clone() {
1124 try {
1125 @SuppressWarnings("unchecked")
1126 ConcurrentSkipListMap<K,V> clone =
1127 (ConcurrentSkipListMap<K,V>) super.clone();
1128 clone.keySet = null;
1129 clone.entrySet = null;
1130 clone.values = null;
1131 clone.descendingMap = null;
1132 clone.adder = null;
1133 clone.buildFromSorted(this);
1134 return clone;
1135 } catch (CloneNotSupportedException e) {
1136 throw new InternalError();
1137 }
1138 }
1139
1140 /**
1141 * Streamlined bulk insertion to initialize from elements of
1142 * given sorted map. Call only from constructor or clone
1143 * method.
1144 */
1145 private void buildFromSorted(SortedMap<K, ? extends V> map) {
1146 if (map == null)
1147 throw new NullPointerException();
1148 Iterator<? extends Map.Entry<? extends K, ? extends V>> it =
1149 map.entrySet().iterator();
1150
1151 /*
1152 * Add equally spaced indices at log intervals, using the bits
1153 * of count during insertion. The maximum possible resulting
1154 * level is less than the number of bits in a long (64). The
1155 * preds array tracks the current rightmost node at each
1156 * level.
1157 */
1158 @SuppressWarnings("unchecked")
1159 Index<K,V>[] preds = (Index<K,V>[])new Index<?,?>[64];
1160 Node<K,V> bp = new Node<K,V>(null, null, null);
1161 Index<K,V> h = preds[0] = new Index<K,V>(bp, null, null);
1162 long count = 0;
1163
1164 while (it.hasNext()) {
1165 Map.Entry<? extends K, ? extends V> e = it.next();
1166 K k = e.getKey();
1167 V v = e.getValue();
1168 if (k == null || v == null)
1169 throw new NullPointerException();
1170 Node<K,V> z = new Node<K,V>(k, v, null);
1171 bp = bp.next = z;
1172 if ((++count & 3L) == 0L) {
1173 long m = count >>> 2;
1174 int i = 0;
1175 Index<K,V> idx = null, q;
1176 do {
1177 idx = new Index<K,V>(z, idx, null);
1178 if ((q = preds[i]) == null)
1179 preds[i] = h = new Index<K,V>(h.node, h, idx);
1180 else
1181 preds[i] = q.right = idx;
1182 } while (++i < preds.length && ((m >>>= 1) & 1L) != 0L);
1183 }
1184 }
1185 if (count != 0L) {
1186 VarHandle.releaseFence(); // emulate volatile stores
1187 addCount(count);
1188 head = h;
1189 VarHandle.fullFence();
1190 }
1191 }
1192
1193 /* ---------------- Serialization -------------- */
1194
1195 /**
1196 * Saves this map to a stream (that is, serializes it).
1197 *
1198 * @param s the stream
1199 * @throws java.io.IOException if an I/O error occurs
1200 * @serialData The key (Object) and value (Object) for each
1201 * key-value mapping represented by the map, followed by
1202 * {@code null}. The key-value mappings are emitted in key-order
1203 * (as determined by the Comparator, or by the keys' natural
1204 * ordering if no Comparator).
1205 */
1206 private void writeObject(java.io.ObjectOutputStream s)
1207 throws java.io.IOException {
1208 // Write out the Comparator and any hidden stuff
1209 s.defaultWriteObject();
1210
1211 // Write out keys and values (alternating)
1212 Node<K,V> b, n; V v;
1213 if ((b = baseHead()) != null) {
1214 while ((n = b.next) != null) {
1215 if ((v = n.val) != null) {
1216 s.writeObject(n.key);
1217 s.writeObject(v);
1218 }
1219 b = n;
1220 }
1221 }
1222 s.writeObject(null);
1223 }
1224
1225 /**
1226 * Reconstitutes this map from a stream (that is, deserializes it).
1227 * @param s the stream
1228 * @throws ClassNotFoundException if the class of a serialized object
1229 * could not be found
1230 * @throws java.io.IOException if an I/O error occurs
1231 */
1232 @SuppressWarnings("unchecked")
1233 private void readObject(final java.io.ObjectInputStream s)
1234 throws java.io.IOException, ClassNotFoundException {
1235 // Read in the Comparator and any hidden stuff
1236 s.defaultReadObject();
1237
1238 // Same idea as buildFromSorted
1239 @SuppressWarnings("unchecked")
1240 Index<K,V>[] preds = (Index<K,V>[])new Index<?,?>[64];
1241 Node<K,V> bp = new Node<K,V>(null, null, null);
1242 Index<K,V> h = preds[0] = new Index<K,V>(bp, null, null);
1243 Comparator<? super K> cmp = comparator;
1244 K prevKey = null;
1245 long count = 0;
1246
1247 for (;;) {
1248 K k = (K)s.readObject();
1249 if (k == null)
1250 break;
1251 V v = (V)s.readObject();
1252 if (v == null)
1253 throw new NullPointerException();
1254 if (prevKey != null && cpr(cmp, prevKey, k) > 0)
1255 throw new IllegalStateException("out of order");
1256 prevKey = k;
1257 Node<K,V> z = new Node<K,V>(k, v, null);
1258 bp = bp.next = z;
1259 if ((++count & 3L) == 0L) {
1260 long m = count >>> 2;
1261 int i = 0;
1262 Index<K,V> idx = null, q;
1263 do {
1264 idx = new Index<K,V>(z, idx, null);
1265 if ((q = preds[i]) == null)
1266 preds[i] = h = new Index<K,V>(h.node, h, idx);
1267 else
1268 preds[i] = q.right = idx;
1269 } while (++i < preds.length && ((m >>>= 1) & 1L) != 0L);
1270 }
1271 }
1272 if (count != 0L) {
1273 VarHandle.releaseFence();
1274 addCount(count);
1275 head = h;
1276 VarHandle.fullFence();
1277 }
1278 }
1279
1280 /* ------ Map API methods ------ */
1281
1282 /**
1283 * Returns {@code true} if this map contains a mapping for the specified
1284 * key.
1285 *
1286 * @param key key whose presence in this map is to be tested
1287 * @return {@code true} if this map contains a mapping for the specified key
1288 * @throws ClassCastException if the specified key cannot be compared
1289 * with the keys currently in the map
1290 * @throws NullPointerException if the specified key is null
1291 */
1292 public boolean containsKey(Object key) {
1293 return doGet(key) != null;
1294 }
1295
1296 /**
1297 * Returns the value to which the specified key is mapped,
1298 * or {@code null} if this map contains no mapping for the key.
1299 *
1300 * <p>More formally, if this map contains a mapping from a key
1301 * {@code k} to a value {@code v} such that {@code key} compares
1302 * equal to {@code k} according to the map's ordering, then this
1303 * method returns {@code v}; otherwise it returns {@code null}.
1304 * (There can be at most one such mapping.)
1305 *
1306 * @throws ClassCastException if the specified key cannot be compared
1307 * with the keys currently in the map
1308 * @throws NullPointerException if the specified key is null
1309 */
1310 public V get(Object key) {
1311 return doGet(key);
1312 }
1313
1314 /**
1315 * Returns the value to which the specified key is mapped,
1316 * or the given defaultValue if this map contains no mapping for the key.
1317 *
1318 * @param key the key
1319 * @param defaultValue the value to return if this map contains
1320 * no mapping for the given key
1321 * @return the mapping for the key, if present; else the defaultValue
1322 * @throws NullPointerException if the specified key is null
1323 * @since 1.8
1324 */
1325 public V getOrDefault(Object key, V defaultValue) {
1326 V v;
1327 return (v = doGet(key)) == null ? defaultValue : v;
1328 }
1329
1330 /**
1331 * Associates the specified value with the specified key in this map.
1332 * If the map previously contained a mapping for the key, the old
1333 * value is replaced.
1334 *
1335 * @param key key with which the specified value is to be associated
1336 * @param value value to be associated with the specified key
1337 * @return the previous value associated with the specified key, or
1338 * {@code null} if there was no mapping for the key
1339 * @throws ClassCastException if the specified key cannot be compared
1340 * with the keys currently in the map
1341 * @throws NullPointerException if the specified key or value is null
1342 */
1343 public V put(K key, V value) {
1344 if (value == null)
1345 throw new NullPointerException();
1346 return doPut(key, value, false);
1347 }
1348
1349 /**
1350 * Removes the mapping for the specified key from this map if present.
1351 *
1352 * @param key key for which mapping should be removed
1353 * @return the previous value associated with the specified key, or
1354 * {@code null} if there was no mapping for the key
1355 * @throws ClassCastException if the specified key cannot be compared
1356 * with the keys currently in the map
1357 * @throws NullPointerException if the specified key is null
1358 */
1359 public V remove(Object key) {
1360 return doRemove(key, null);
1361 }
1362
1363 /**
1364 * Returns {@code true} if this map maps one or more keys to the
1365 * specified value. This operation requires time linear in the
1366 * map size. Additionally, it is possible for the map to change
1367 * during execution of this method, in which case the returned
1368 * result may be inaccurate.
1369 *
1370 * @param value value whose presence in this map is to be tested
1371 * @return {@code true} if a mapping to {@code value} exists;
1372 * {@code false} otherwise
1373 * @throws NullPointerException if the specified value is null
1374 */
1375 public boolean containsValue(Object value) {
1376 if (value == null)
1377 throw new NullPointerException();
1378 Node<K,V> b, n; V v;
1379 if ((b = baseHead()) != null) {
1380 while ((n = b.next) != null) {
1381 if ((v = n.val) != null && value.equals(v))
1382 return true;
1383 else
1384 b = n;
1385 }
1386 }
1387 return false;
1388 }
1389
1390 /**
1391 * {@inheritDoc}
1392 */
1393 public int size() {
1394 long c;
1395 return ((baseHead() == null) ? 0 :
1396 ((c = getAdderCount()) >= Integer.MAX_VALUE) ?
1397 Integer.MAX_VALUE : (int) c);
1398 }
1399
1400 /**
1401 * {@inheritDoc}
1402 */
1403 public boolean isEmpty() {
1404 return findFirst() == null;
1405 }
1406
1407 /**
1408 * Removes all of the mappings from this map.
1409 */
1410 public void clear() {
1411 Index<K,V> h, r, d; Node<K,V> b;
1412 VarHandle.acquireFence();
1413 while ((h = head) != null) {
1414 if ((r = h.right) != null) // remove indices
1415 RIGHT.compareAndSet(h, r, null);
1416 else if ((d = h.down) != null) // remove levels
1417 HEAD.compareAndSet(this, h, d);
1418 else {
1419 long count = 0L;
1420 if ((b = h.node) != null) { // remove nodes
1421 Node<K,V> n; V v;
1422 while ((n = b.next) != null) {
1423 if ((v = n.val) != null &&
1424 VAL.compareAndSet(n, v, null)) {
1425 --count;
1426 v = null;
1427 }
1428 if (v == null)
1429 unlinkNode(b, n);
1430 }
1431 }
1432 if (count != 0L)
1433 addCount(count);
1434 else
1435 break;
1436 }
1437 }
1438 }
1439
1440 /**
1441 * If the specified key is not already associated with a value,
1442 * attempts to compute its value using the given mapping function
1443 * and enters it into this map unless {@code null}. The function
1444 * is <em>NOT</em> guaranteed to be applied once atomically only
1445 * if the value is not present.
1446 *
1447 * @param key key with which the specified value is to be associated
1448 * @param mappingFunction the function to compute a value
1449 * @return the current (existing or computed) value associated with
1450 * the specified key, or null if the computed value is null
1451 * @throws NullPointerException if the specified key is null
1452 * or the mappingFunction is null
1453 * @since 1.8
1454 */
1455 public V computeIfAbsent(K key,
1456 Function<? super K, ? extends V> mappingFunction) {
1457 if (key == null || mappingFunction == null)
1458 throw new NullPointerException();
1459 V v, p, r;
1460 if ((v = doGet(key)) == null &&
1461 (r = mappingFunction.apply(key)) != null)
1462 v = (p = doPut(key, r, true)) == null ? r : p;
1463 return v;
1464 }
1465
1466 /**
1467 * If the value for the specified key is present, attempts to
1468 * compute a new mapping given the key and its current mapped
1469 * value. The function is <em>NOT</em> guaranteed to be applied
1470 * once atomically.
1471 *
1472 * @param key key with which a value may be associated
1473 * @param remappingFunction the function to compute a value
1474 * @return the new value associated with the specified key, or null if none
1475 * @throws NullPointerException if the specified key is null
1476 * or the remappingFunction is null
1477 * @since 1.8
1478 */
1479 public V computeIfPresent(K key,
1480 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1481 if (key == null || remappingFunction == null)
1482 throw new NullPointerException();
1483 Node<K,V> n; V v;
1484 while ((n = findNode(key)) != null) {
1485 if ((v = n.val) != null) {
1486 V r = remappingFunction.apply(key, v);
1487 if (r != null) {
1488 if (VAL.compareAndSet(n, v, r))
1489 return r;
1490 }
1491 else if (doRemove(key, v) != null)
1492 break;
1493 }
1494 }
1495 return null;
1496 }
1497
1498 /**
1499 * Attempts to compute a mapping for the specified key and its
1500 * current mapped value (or {@code null} if there is no current
1501 * mapping). The function is <em>NOT</em> guaranteed to be applied
1502 * once atomically.
1503 *
1504 * @param key key with which the specified value is to be associated
1505 * @param remappingFunction the function to compute a value
1506 * @return the new value associated with the specified key, or null if none
1507 * @throws NullPointerException if the specified key is null
1508 * or the remappingFunction is null
1509 * @since 1.8
1510 */
1511 public V compute(K key,
1512 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1513 if (key == null || remappingFunction == null)
1514 throw new NullPointerException();
1515 for (;;) {
1516 Node<K,V> n; V v; V r;
1517 if ((n = findNode(key)) == null) {
1518 if ((r = remappingFunction.apply(key, null)) == null)
1519 break;
1520 if (doPut(key, r, true) == null)
1521 return r;
1522 }
1523 else if ((v = n.val) != null) {
1524 if ((r = remappingFunction.apply(key, v)) != null) {
1525 if (VAL.compareAndSet(n, v, r))
1526 return r;
1527 }
1528 else if (doRemove(key, v) != null)
1529 break;
1530 }
1531 }
1532 return null;
1533 }
1534
1535 /**
1536 * If the specified key is not already associated with a value,
1537 * associates it with the given value. Otherwise, replaces the
1538 * value with the results of the given remapping function, or
1539 * removes if {@code null}. The function is <em>NOT</em>
1540 * guaranteed to be applied once atomically.
1541 *
1542 * @param key key with which the specified value is to be associated
1543 * @param value the value to use if absent
1544 * @param remappingFunction the function to recompute a value if present
1545 * @return the new value associated with the specified key, or null if none
1546 * @throws NullPointerException if the specified key or value is null
1547 * or the remappingFunction is null
1548 * @since 1.8
1549 */
1550 public V merge(K key, V value,
1551 BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1552 if (key == null || value == null || remappingFunction == null)
1553 throw new NullPointerException();
1554 for (;;) {
1555 Node<K,V> n; V v; V r;
1556 if ((n = findNode(key)) == null) {
1557 if (doPut(key, value, true) == null)
1558 return value;
1559 }
1560 else if ((v = n.val) != null) {
1561 if ((r = remappingFunction.apply(v, value)) != null) {
1562 if (VAL.compareAndSet(n, v, r))
1563 return r;
1564 }
1565 else if (doRemove(key, v) != null)
1566 return null;
1567 }
1568 }
1569 }
1570
1571 /* ---------------- View methods -------------- */
1572
1573 /*
1574 * Note: Lazy initialization works for views because view classes
1575 * are stateless/immutable so it doesn't matter wrt correctness if
1576 * more than one is created (which will only rarely happen). Even
1577 * so, the following idiom conservatively ensures that the method
1578 * returns the one it created if it does so, not one created by
1579 * another racing thread.
1580 */
1581
1582 /**
1583 * Returns a {@link NavigableSet} view of the keys contained in this map.
1584 *
1585 * <p>The set's iterator returns the keys in ascending order.
1586 * The set's spliterator additionally reports {@link Spliterator#CONCURRENT},
1587 * {@link Spliterator#NONNULL}, {@link Spliterator#SORTED} and
1588 * {@link Spliterator#ORDERED}, with an encounter order that is ascending
1589 * key order.
1590 *
1591 * <p>The {@linkplain Spliterator#getComparator() spliterator's comparator}
1592 * is {@code null} if the {@linkplain #comparator() map's comparator}
1593 * is {@code null}.
1594 * Otherwise, the spliterator's comparator is the same as or imposes the
1595 * same total ordering as the map's comparator.
1596 *
1597 * <p>The set is backed by the map, so changes to the map are
1598 * reflected in the set, and vice-versa. The set supports element
1599 * removal, which removes the corresponding mapping from the map,
1600 * via the {@code Iterator.remove}, {@code Set.remove},
1601 * {@code removeAll}, {@code retainAll}, and {@code clear}
1602 * operations. It does not support the {@code add} or {@code addAll}
1603 * operations.
1604 *
1605 * <p>The view's iterators and spliterators are
1606 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1607 *
1608 * <p>This method is equivalent to method {@code navigableKeySet}.
1609 *
1610 * @return a navigable set view of the keys in this map
1611 */
1612 public NavigableSet<K> keySet() {
1613 KeySet<K,V> ks;
1614 if ((ks = keySet) != null) return ks;
1615 return keySet = new KeySet<>(this);
1616 }
1617
1618 public NavigableSet<K> navigableKeySet() {
1619 KeySet<K,V> ks;
1620 if ((ks = keySet) != null) return ks;
1621 return keySet = new KeySet<>(this);
1622 }
1623
1624 /**
1625 * Returns a {@link Collection} view of the values contained in this map.
1626 * <p>The collection's iterator returns the values in ascending order
1627 * of the corresponding keys. The collections's spliterator additionally
1628 * reports {@link Spliterator#CONCURRENT}, {@link Spliterator#NONNULL} and
1629 * {@link Spliterator#ORDERED}, with an encounter order that is ascending
1630 * order of the corresponding keys.
1631 *
1632 * <p>The collection is backed by the map, so changes to the map are
1633 * reflected in the collection, and vice-versa. The collection
1634 * supports element removal, which removes the corresponding
1635 * mapping from the map, via the {@code Iterator.remove},
1636 * {@code Collection.remove}, {@code removeAll},
1637 * {@code retainAll} and {@code clear} operations. It does not
1638 * support the {@code add} or {@code addAll} operations.
1639 *
1640 * <p>The view's iterators and spliterators are
1641 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1642 */
1643 public Collection<V> values() {
1644 Values<K,V> vs;
1645 if ((vs = values) != null) return vs;
1646 return values = new Values<>(this);
1647 }
1648
1649 /**
1650 * Returns a {@link Set} view of the mappings contained in this map.
1651 *
1652 * <p>The set's iterator returns the entries in ascending key order. The
1653 * set's spliterator additionally reports {@link Spliterator#CONCURRENT},
1654 * {@link Spliterator#NONNULL}, {@link Spliterator#SORTED} and
1655 * {@link Spliterator#ORDERED}, with an encounter order that is ascending
1656 * key order.
1657 *
1658 * <p>The set is backed by the map, so changes to the map are
1659 * reflected in the set, and vice-versa. The set supports element
1660 * removal, which removes the corresponding mapping from the map,
1661 * via the {@code Iterator.remove}, {@code Set.remove},
1662 * {@code removeAll}, {@code retainAll} and {@code clear}
1663 * operations. It does not support the {@code add} or
1664 * {@code addAll} operations.
1665 *
1666 * <p>The view's iterators and spliterators are
1667 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1668 *
1669 * <p>The {@code Map.Entry} elements traversed by the {@code iterator}
1670 * or {@code spliterator} do <em>not</em> support the {@code setValue}
1671 * operation.
1672 *
1673 * @return a set view of the mappings contained in this map,
1674 * sorted in ascending key order
1675 */
1676 public Set<Map.Entry<K,V>> entrySet() {
1677 EntrySet<K,V> es;
1678 if ((es = entrySet) != null) return es;
1679 return entrySet = new EntrySet<K,V>(this);
1680 }
1681
1682 public ConcurrentNavigableMap<K,V> descendingMap() {
1683 ConcurrentNavigableMap<K,V> dm;
1684 if ((dm = descendingMap) != null) return dm;
1685 return descendingMap =
1686 new SubMap<K,V>(this, null, false, null, false, true);
1687 }
1688
1689 public NavigableSet<K> descendingKeySet() {
1690 return descendingMap().navigableKeySet();
1691 }
1692
1693 /* ---------------- AbstractMap Overrides -------------- */
1694
1695 /**
1696 * Compares the specified object with this map for equality.
1697 * Returns {@code true} if the given object is also a map and the
1698 * two maps represent the same mappings. More formally, two maps
1699 * {@code m1} and {@code m2} represent the same mappings if
1700 * {@code m1.entrySet().equals(m2.entrySet())}. This
1701 * operation may return misleading results if either map is
1702 * concurrently modified during execution of this method.
1703 *
1704 * @param o object to be compared for equality with this map
1705 * @return {@code true} if the specified object is equal to this map
1706 */
1707 public boolean equals(Object o) {
1708 if (o == this)
1709 return true;
1710 if (!(o instanceof Map))
1711 return false;
1712 Map<?,?> m = (Map<?,?>) o;
1713 try {
1714 Comparator<? super K> cmp = comparator;
1715 // See JDK-8223553 for Iterator type wildcard rationale
1716 Iterator<? extends Map.Entry<?,?>> it = m.entrySet().iterator();
1717 if (m instanceof SortedMap &&
1718 ((SortedMap<?,?>)m).comparator() == cmp) {
1719 Node<K,V> b, n;
1720 if ((b = baseHead()) != null) {
1721 while ((n = b.next) != null) {
1722 K k; V v;
1723 if ((v = n.val) != null && (k = n.key) != null) {
1724 if (!it.hasNext())
1725 return false;
1726 Map.Entry<?,?> e = it.next();
1727 Object mk = e.getKey();
1728 Object mv = e.getValue();
1729 if (mk == null || mv == null)
1730 return false;
1731 try {
1732 if (cpr(cmp, k, mk) != 0)
1733 return false;
1734 } catch (ClassCastException cce) {
1735 return false;
1736 }
1737 if (!mv.equals(v))
1738 return false;
1739 }
1740 b = n;
1741 }
1742 }
1743 return !it.hasNext();
1744 }
1745 else {
1746 while (it.hasNext()) {
1747 V v;
1748 Map.Entry<?,?> e = it.next();
1749 Object mk = e.getKey();
1750 Object mv = e.getValue();
1751 if (mk == null || mv == null ||
1752 (v = get(mk)) == null || !v.equals(mv))
1753 return false;
1754 }
1755 Node<K,V> b, n;
1756 if ((b = baseHead()) != null) {
1757 K k; V v; Object mv;
1758 while ((n = b.next) != null) {
1759 if ((v = n.val) != null && (k = n.key) != null &&
1760 ((mv = m.get(k)) == null || !mv.equals(v)))
1761 return false;
1762 b = n;
1763 }
1764 }
1765 return true;
1766 }
1767 } catch (ClassCastException | NullPointerException unused) {
1768 return false;
1769 }
1770 }
1771
1772 /* ------ ConcurrentMap API methods ------ */
1773
1774 /**
1775 * {@inheritDoc}
1776 *
1777 * @return the previous value associated with the specified key,
1778 * or {@code null} if there was no mapping for the key
1779 * @throws ClassCastException if the specified key cannot be compared
1780 * with the keys currently in the map
1781 * @throws NullPointerException if the specified key or value is null
1782 */
1783 public V putIfAbsent(K key, V value) {
1784 if (value == null)
1785 throw new NullPointerException();
1786 return doPut(key, value, true);
1787 }
1788
1789 /**
1790 * {@inheritDoc}
1791 *
1792 * @throws ClassCastException if the specified key cannot be compared
1793 * with the keys currently in the map
1794 * @throws NullPointerException if the specified key is null
1795 */
1796 public boolean remove(Object key, Object value) {
1797 if (key == null)
1798 throw new NullPointerException();
1799 return value != null && doRemove(key, value) != null;
1800 }
1801
1802 /**
1803 * {@inheritDoc}
1804 *
1805 * @throws ClassCastException if the specified key cannot be compared
1806 * with the keys currently in the map
1807 * @throws NullPointerException if any of the arguments are null
1808 */
1809 public boolean replace(K key, V oldValue, V newValue) {
1810 if (key == null || oldValue == null || newValue == null)
1811 throw new NullPointerException();
1812 for (;;) {
1813 Node<K,V> n; V v;
1814 if ((n = findNode(key)) == null)
1815 return false;
1816 if ((v = n.val) != null) {
1817 if (!oldValue.equals(v))
1818 return false;
1819 if (VAL.compareAndSet(n, v, newValue))
1820 return true;
1821 }
1822 }
1823 }
1824
1825 /**
1826 * {@inheritDoc}
1827 *
1828 * @return the previous value associated with the specified key,
1829 * or {@code null} if there was no mapping for the key
1830 * @throws ClassCastException if the specified key cannot be compared
1831 * with the keys currently in the map
1832 * @throws NullPointerException if the specified key or value is null
1833 */
1834 public V replace(K key, V value) {
1835 if (key == null || value == null)
1836 throw new NullPointerException();
1837 for (;;) {
1838 Node<K,V> n; V v;
1839 if ((n = findNode(key)) == null)
1840 return null;
1841 if ((v = n.val) != null && VAL.compareAndSet(n, v, value))
1842 return v;
1843 }
1844 }
1845
1846 /* ------ SortedMap API methods ------ */
1847
1848 public Comparator<? super K> comparator() {
1849 return comparator;
1850 }
1851
1852 /**
1853 * @throws NoSuchElementException {@inheritDoc}
1854 */
1855 public K firstKey() {
1856 Node<K,V> n = findFirst();
1857 if (n == null)
1858 throw new NoSuchElementException();
1859 return n.key;
1860 }
1861
1862 /**
1863 * @throws NoSuchElementException {@inheritDoc}
1864 */
1865 public K lastKey() {
1866 Node<K,V> n = findLast();
1867 if (n == null)
1868 throw new NoSuchElementException();
1869 return n.key;
1870 }
1871
1872 /**
1873 * @throws ClassCastException {@inheritDoc}
1874 * @throws NullPointerException if {@code fromKey} or {@code toKey} is null
1875 * @throws IllegalArgumentException {@inheritDoc}
1876 */
1877 public ConcurrentNavigableMap<K,V> subMap(K fromKey,
1878 boolean fromInclusive,
1879 K toKey,
1880 boolean toInclusive) {
1881 if (fromKey == null || toKey == null)
1882 throw new NullPointerException();
1883 return new SubMap<K,V>
1884 (this, fromKey, fromInclusive, toKey, toInclusive, false);
1885 }
1886
1887 /**
1888 * @throws ClassCastException {@inheritDoc}
1889 * @throws NullPointerException if {@code toKey} is null
1890 * @throws IllegalArgumentException {@inheritDoc}
1891 */
1892 public ConcurrentNavigableMap<K,V> headMap(K toKey,
1893 boolean inclusive) {
1894 if (toKey == null)
1895 throw new NullPointerException();
1896 return new SubMap<K,V>
1897 (this, null, false, toKey, inclusive, false);
1898 }
1899
1900 /**
1901 * @throws ClassCastException {@inheritDoc}
1902 * @throws NullPointerException if {@code fromKey} is null
1903 * @throws IllegalArgumentException {@inheritDoc}
1904 */
1905 public ConcurrentNavigableMap<K,V> tailMap(K fromKey,
1906 boolean inclusive) {
1907 if (fromKey == null)
1908 throw new NullPointerException();
1909 return new SubMap<K,V>
1910 (this, fromKey, inclusive, null, false, false);
1911 }
1912
1913 /**
1914 * @throws ClassCastException {@inheritDoc}
1915 * @throws NullPointerException if {@code fromKey} or {@code toKey} is null
1916 * @throws IllegalArgumentException {@inheritDoc}
1917 */
1918 public ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey) {
1919 return subMap(fromKey, true, toKey, false);
1920 }
1921
1922 /**
1923 * @throws ClassCastException {@inheritDoc}
1924 * @throws NullPointerException if {@code toKey} is null
1925 * @throws IllegalArgumentException {@inheritDoc}
1926 */
1927 public ConcurrentNavigableMap<K,V> headMap(K toKey) {
1928 return headMap(toKey, false);
1929 }
1930
1931 /**
1932 * @throws ClassCastException {@inheritDoc}
1933 * @throws NullPointerException if {@code fromKey} is null
1934 * @throws IllegalArgumentException {@inheritDoc}
1935 */
1936 public ConcurrentNavigableMap<K,V> tailMap(K fromKey) {
1937 return tailMap(fromKey, true);
1938 }
1939
1940 /* ---------------- Relational operations -------------- */
1941
1942 /**
1943 * Returns a key-value mapping associated with the greatest key
1944 * strictly less than the given key, or {@code null} if there is
1945 * no such key. The returned entry does <em>not</em> support the
1946 * {@code Entry.setValue} method.
1947 *
1948 * @throws ClassCastException {@inheritDoc}
1949 * @throws NullPointerException if the specified key is null
1950 */
1951 public Map.Entry<K,V> lowerEntry(K key) {
1952 return findNearEntry(key, LT, comparator);
1953 }
1954
1955 /**
1956 * @throws ClassCastException {@inheritDoc}
1957 * @throws NullPointerException if the specified key is null
1958 */
1959 public K lowerKey(K key) {
1960 Node<K,V> n = findNear(key, LT, comparator);
1961 return (n == null) ? null : n.key;
1962 }
1963
1964 /**
1965 * Returns a key-value mapping associated with the greatest key
1966 * less than or equal to the given key, or {@code null} if there
1967 * is no such key. The returned entry does <em>not</em> support
1968 * the {@code Entry.setValue} method.
1969 *
1970 * @param key the key
1971 * @throws ClassCastException {@inheritDoc}
1972 * @throws NullPointerException if the specified key is null
1973 */
1974 public Map.Entry<K,V> floorEntry(K key) {
1975 return findNearEntry(key, LT|EQ, comparator);
1976 }
1977
1978 /**
1979 * @param key the key
1980 * @throws ClassCastException {@inheritDoc}
1981 * @throws NullPointerException if the specified key is null
1982 */
1983 public K floorKey(K key) {
1984 Node<K,V> n = findNear(key, LT|EQ, comparator);
1985 return (n == null) ? null : n.key;
1986 }
1987
1988 /**
1989 * Returns a key-value mapping associated with the least key
1990 * greater than or equal to the given key, or {@code null} if
1991 * there is no such entry. The returned entry does <em>not</em>
1992 * support the {@code Entry.setValue} method.
1993 *
1994 * @throws ClassCastException {@inheritDoc}
1995 * @throws NullPointerException if the specified key is null
1996 */
1997 public Map.Entry<K,V> ceilingEntry(K key) {
1998 return findNearEntry(key, GT|EQ, comparator);
1999 }
2000
2001 /**
2002 * @throws ClassCastException {@inheritDoc}
2003 * @throws NullPointerException if the specified key is null
2004 */
2005 public K ceilingKey(K key) {
2006 Node<K,V> n = findNear(key, GT|EQ, comparator);
2007 return (n == null) ? null : n.key;
2008 }
2009
2010 /**
2011 * Returns a key-value mapping associated with the least key
2012 * strictly greater than the given key, or {@code null} if there
2013 * is no such key. The returned entry does <em>not</em> support
2014 * the {@code Entry.setValue} method.
2015 *
2016 * @param key the key
2017 * @throws ClassCastException {@inheritDoc}
2018 * @throws NullPointerException if the specified key is null
2019 */
2020 public Map.Entry<K,V> higherEntry(K key) {
2021 return findNearEntry(key, GT, comparator);
2022 }
2023
2024 /**
2025 * @param key the key
2026 * @throws ClassCastException {@inheritDoc}
2027 * @throws NullPointerException if the specified key is null
2028 */
2029 public K higherKey(K key) {
2030 Node<K,V> n = findNear(key, GT, comparator);
2031 return (n == null) ? null : n.key;
2032 }
2033
2034 /**
2035 * Returns a key-value mapping associated with the least
2036 * key in this map, or {@code null} if the map is empty.
2037 * The returned entry does <em>not</em> support
2038 * the {@code Entry.setValue} method.
2039 */
2040 public Map.Entry<K,V> firstEntry() {
2041 return findFirstEntry();
2042 }
2043
2044 /**
2045 * Returns a key-value mapping associated with the greatest
2046 * key in this map, or {@code null} if the map is empty.
2047 * The returned entry does <em>not</em> support
2048 * the {@code Entry.setValue} method.
2049 */
2050 public Map.Entry<K,V> lastEntry() {
2051 return findLastEntry();
2052 }
2053
2054 /**
2055 * Removes and returns a key-value mapping associated with
2056 * the least key in this map, or {@code null} if the map is empty.
2057 * The returned entry does <em>not</em> support
2058 * the {@code Entry.setValue} method.
2059 */
2060 public Map.Entry<K,V> pollFirstEntry() {
2061 return doRemoveFirstEntry();
2062 }
2063
2064 /**
2065 * Removes and returns a key-value mapping associated with
2066 * the greatest key in this map, or {@code null} if the map is empty.
2067 * The returned entry does <em>not</em> support
2068 * the {@code Entry.setValue} method.
2069 */
2070 public Map.Entry<K,V> pollLastEntry() {
2071 return doRemoveLastEntry();
2072 }
2073
2074 /* ---------------- Iterators -------------- */
2075
2076 /**
2077 * Base of iterator classes
2078 */
2079 abstract class Iter<T> implements Iterator<T> {
2080 /** the last node returned by next() */
2081 Node<K,V> lastReturned;
2082 /** the next node to return from next(); */
2083 Node<K,V> next;
2084 /** Cache of next value field to maintain weak consistency */
2085 V nextValue;
2086
2087 /** Initializes ascending iterator for entire range. */
2088 Iter() {
2089 advance(baseHead());
2090 }
2091
2092 public final boolean hasNext() {
2093 return next != null;
2094 }
2095
2096 /** Advances next to higher entry. */
2097 final void advance(Node<K,V> b) {
2098 Node<K,V> n = null;
2099 V v = null;
2100 if ((lastReturned = b) != null) {
2101 while ((n = b.next) != null && (v = n.val) == null)
2102 b = n;
2103 }
2104 nextValue = v;
2105 next = n;
2106 }
2107
2108 public final void remove() {
2109 Node<K,V> n; K k;
2110 if ((n = lastReturned) == null || (k = n.key) == null)
2111 throw new IllegalStateException();
2112 // It would not be worth all of the overhead to directly
2113 // unlink from here. Using remove is fast enough.
2114 ConcurrentSkipListMap.this.remove(k);
2115 lastReturned = null;
2116 }
2117 }
2118
2119 final class ValueIterator extends Iter<V> {
2120 public V next() {
2121 V v;
2122 if ((v = nextValue) == null)
2123 throw new NoSuchElementException();
2124 advance(next);
2125 return v;
2126 }
2127 }
2128
2129 final class KeyIterator extends Iter<K> {
2130 public K next() {
2131 Node<K,V> n;
2132 if ((n = next) == null)
2133 throw new NoSuchElementException();
2134 K k = n.key;
2135 advance(n);
2136 return k;
2137 }
2138 }
2139
2140 final class EntryIterator extends Iter<Map.Entry<K,V>> {
2141 public Map.Entry<K,V> next() {
2142 Node<K,V> n;
2143 if ((n = next) == null)
2144 throw new NoSuchElementException();
2145 K k = n.key;
2146 V v = nextValue;
2147 advance(n);
2148 return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2149 }
2150 }
2151
2152 /* ---------------- View Classes -------------- */
2153
2154 /*
2155 * View classes are static, delegating to a ConcurrentNavigableMap
2156 * to allow use by SubMaps, which outweighs the ugliness of
2157 * needing type-tests for Iterator methods.
2158 */
2159
2160 static final <E> List<E> toList(Collection<E> c) {
2161 // Using size() here would be a pessimization.
2162 ArrayList<E> list = new ArrayList<E>();
2163 for (E e : c)
2164 list.add(e);
2165 return list;
2166 }
2167
2168 static final class KeySet<K,V>
2169 extends AbstractSet<K> implements NavigableSet<K> {
2170 final ConcurrentNavigableMap<K,V> m;
2171 KeySet(ConcurrentNavigableMap<K,V> map) { m = map; }
2172 public int size() { return m.size(); }
2173 public boolean isEmpty() { return m.isEmpty(); }
2174 public boolean contains(Object o) { return m.containsKey(o); }
2175 public boolean remove(Object o) { return m.remove(o) != null; }
2176 public void clear() { m.clear(); }
2177 public K lower(K e) { return m.lowerKey(e); }
2178 public K floor(K e) { return m.floorKey(e); }
2179 public K ceiling(K e) { return m.ceilingKey(e); }
2180 public K higher(K e) { return m.higherKey(e); }
2181 public Comparator<? super K> comparator() { return m.comparator(); }
2182 public K first() { return m.firstKey(); }
2183 public K last() { return m.lastKey(); }
2184 public K pollFirst() {
2185 Map.Entry<K,V> e = m.pollFirstEntry();
2186 return (e == null) ? null : e.getKey();
2187 }
2188 public K pollLast() {
2189 Map.Entry<K,V> e = m.pollLastEntry();
2190 return (e == null) ? null : e.getKey();
2191 }
2192 public Iterator<K> iterator() {
2193 return (m instanceof ConcurrentSkipListMap)
2194 ? ((ConcurrentSkipListMap<K,V>)m).new KeyIterator()
2195 : ((SubMap<K,V>)m).new SubMapKeyIterator();
2196 }
2197 public boolean equals(Object o) {
2198 if (o == this)
2199 return true;
2200 if (!(o instanceof Set))
2201 return false;
2202 Collection<?> c = (Collection<?>) o;
2203 try {
2204 return containsAll(c) && c.containsAll(this);
2205 } catch (ClassCastException | NullPointerException unused) {
2206 return false;
2207 }
2208 }
2209 public Object[] toArray() { return toList(this).toArray(); }
2210 public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
2211 public Iterator<K> descendingIterator() {
2212 return descendingSet().iterator();
2213 }
2214 public NavigableSet<K> subSet(K fromElement,
2215 boolean fromInclusive,
2216 K toElement,
2217 boolean toInclusive) {
2218 return new KeySet<>(m.subMap(fromElement, fromInclusive,
2219 toElement, toInclusive));
2220 }
2221 public NavigableSet<K> headSet(K toElement, boolean inclusive) {
2222 return new KeySet<>(m.headMap(toElement, inclusive));
2223 }
2224 public NavigableSet<K> tailSet(K fromElement, boolean inclusive) {
2225 return new KeySet<>(m.tailMap(fromElement, inclusive));
2226 }
2227 public NavigableSet<K> subSet(K fromElement, K toElement) {
2228 return subSet(fromElement, true, toElement, false);
2229 }
2230 public NavigableSet<K> headSet(K toElement) {
2231 return headSet(toElement, false);
2232 }
2233 public NavigableSet<K> tailSet(K fromElement) {
2234 return tailSet(fromElement, true);
2235 }
2236 public NavigableSet<K> descendingSet() {
2237 return new KeySet<>(m.descendingMap());
2238 }
2239
2240 public Spliterator<K> spliterator() {
2241 return (m instanceof ConcurrentSkipListMap)
2242 ? ((ConcurrentSkipListMap<K,V>)m).keySpliterator()
2243 : ((SubMap<K,V>)m).new SubMapKeyIterator();
2244 }
2245 }
2246
2247 static final class Values<K,V> extends AbstractCollection<V> {
2248 final ConcurrentNavigableMap<K,V> m;
2249 Values(ConcurrentNavigableMap<K,V> map) {
2250 m = map;
2251 }
2252 public Iterator<V> iterator() {
2253 return (m instanceof ConcurrentSkipListMap)
2254 ? ((ConcurrentSkipListMap<K,V>)m).new ValueIterator()
2255 : ((SubMap<K,V>)m).new SubMapValueIterator();
2256 }
2257 public int size() { return m.size(); }
2258 public boolean isEmpty() { return m.isEmpty(); }
2259 public boolean contains(Object o) { return m.containsValue(o); }
2260 public void clear() { m.clear(); }
2261 public Object[] toArray() { return toList(this).toArray(); }
2262 public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
2263
2264 public Spliterator<V> spliterator() {
2265 return (m instanceof ConcurrentSkipListMap)
2266 ? ((ConcurrentSkipListMap<K,V>)m).valueSpliterator()
2267 : ((SubMap<K,V>)m).new SubMapValueIterator();
2268 }
2269
2270 public boolean removeIf(Predicate<? super V> filter) {
2271 if (filter == null) throw new NullPointerException();
2272 if (m instanceof ConcurrentSkipListMap)
2273 return ((ConcurrentSkipListMap<K,V>)m).removeValueIf(filter);
2274 // else use iterator
2275 Iterator<Map.Entry<K,V>> it =
2276 ((SubMap<K,V>)m).new SubMapEntryIterator();
2277 boolean removed = false;
2278 while (it.hasNext()) {
2279 Map.Entry<K,V> e = it.next();
2280 V v = e.getValue();
2281 if (filter.test(v) && m.remove(e.getKey(), v))
2282 removed = true;
2283 }
2284 return removed;
2285 }
2286 }
2287
2288 static final class EntrySet<K,V> extends AbstractSet<Map.Entry<K,V>> {
2289 final ConcurrentNavigableMap<K,V> m;
2290 EntrySet(ConcurrentNavigableMap<K,V> map) {
2291 m = map;
2292 }
2293 public Iterator<Map.Entry<K,V>> iterator() {
2294 return (m instanceof ConcurrentSkipListMap)
2295 ? ((ConcurrentSkipListMap<K,V>)m).new EntryIterator()
2296 : ((SubMap<K,V>)m).new SubMapEntryIterator();
2297 }
2298
2299 public boolean contains(Object o) {
2300 if (!(o instanceof Map.Entry))
2301 return false;
2302 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
2303 V v = m.get(e.getKey());
2304 return v != null && v.equals(e.getValue());
2305 }
2306 public boolean remove(Object o) {
2307 if (!(o instanceof Map.Entry))
2308 return false;
2309 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
2310 return m.remove(e.getKey(),
2311 e.getValue());
2312 }
2313 public boolean isEmpty() {
2314 return m.isEmpty();
2315 }
2316 public int size() {
2317 return m.size();
2318 }
2319 public void clear() {
2320 m.clear();
2321 }
2322 public boolean equals(Object o) {
2323 if (o == this)
2324 return true;
2325 if (!(o instanceof Set))
2326 return false;
2327 Collection<?> c = (Collection<?>) o;
2328 try {
2329 return containsAll(c) && c.containsAll(this);
2330 } catch (ClassCastException | NullPointerException unused) {
2331 return false;
2332 }
2333 }
2334 public Object[] toArray() { return toList(this).toArray(); }
2335 public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
2336
2337 public Spliterator<Map.Entry<K,V>> spliterator() {
2338 return (m instanceof ConcurrentSkipListMap)
2339 ? ((ConcurrentSkipListMap<K,V>)m).entrySpliterator()
2340 : ((SubMap<K,V>)m).new SubMapEntryIterator();
2341 }
2342 public boolean removeIf(Predicate<? super Entry<K,V>> filter) {
2343 if (filter == null) throw new NullPointerException();
2344 if (m instanceof ConcurrentSkipListMap)
2345 return ((ConcurrentSkipListMap<K,V>)m).removeEntryIf(filter);
2346 // else use iterator
2347 Iterator<Map.Entry<K,V>> it =
2348 ((SubMap<K,V>)m).new SubMapEntryIterator();
2349 boolean removed = false;
2350 while (it.hasNext()) {
2351 Map.Entry<K,V> e = it.next();
2352 if (filter.test(e) && m.remove(e.getKey(), e.getValue()))
2353 removed = true;
2354 }
2355 return removed;
2356 }
2357 }
2358
2359 /**
2360 * Submaps returned by {@link ConcurrentSkipListMap} submap operations
2361 * represent a subrange of mappings of their underlying maps.
2362 * Instances of this class support all methods of their underlying
2363 * maps, differing in that mappings outside their range are ignored,
2364 * and attempts to add mappings outside their ranges result in {@link
2365 * IllegalArgumentException}. Instances of this class are constructed
2366 * only using the {@code subMap}, {@code headMap}, and {@code tailMap}
2367 * methods of their underlying maps.
2368 *
2369 * @serial include
2370 */
2371 static final class SubMap<K,V> extends AbstractMap<K,V>
2372 implements ConcurrentNavigableMap<K,V>, Serializable {
2373 private static final long serialVersionUID = -7647078645895051609L;
2374
2375 /** Underlying map */
2376 final ConcurrentSkipListMap<K,V> m;
2377 /** lower bound key, or null if from start */
2378 private final K lo;
2379 /** upper bound key, or null if to end */
2380 private final K hi;
2381 /** inclusion flag for lo */
2382 private final boolean loInclusive;
2383 /** inclusion flag for hi */
2384 private final boolean hiInclusive;
2385 /** direction */
2386 final boolean isDescending;
2387
2388 // Lazily initialized view holders
2389 private transient KeySet<K,V> keySetView;
2390 private transient Values<K,V> valuesView;
2391 private transient EntrySet<K,V> entrySetView;
2392
2393 /**
2394 * Creates a new submap, initializing all fields.
2395 */
2396 SubMap(ConcurrentSkipListMap<K,V> map,
2397 K fromKey, boolean fromInclusive,
2398 K toKey, boolean toInclusive,
2399 boolean isDescending) {
2400 Comparator<? super K> cmp = map.comparator;
2401 if (fromKey != null && toKey != null &&
2402 cpr(cmp, fromKey, toKey) > 0)
2403 throw new IllegalArgumentException("inconsistent range");
2404 this.m = map;
2405 this.lo = fromKey;
2406 this.hi = toKey;
2407 this.loInclusive = fromInclusive;
2408 this.hiInclusive = toInclusive;
2409 this.isDescending = isDescending;
2410 }
2411
2412 /* ---------------- Utilities -------------- */
2413
2414 boolean tooLow(Object key, Comparator<? super K> cmp) {
2415 int c;
2416 return (lo != null && ((c = cpr(cmp, key, lo)) < 0 ||
2417 (c == 0 && !loInclusive)));
2418 }
2419
2420 boolean tooHigh(Object key, Comparator<? super K> cmp) {
2421 int c;
2422 return (hi != null && ((c = cpr(cmp, key, hi)) > 0 ||
2423 (c == 0 && !hiInclusive)));
2424 }
2425
2426 boolean inBounds(Object key, Comparator<? super K> cmp) {
2427 return !tooLow(key, cmp) && !tooHigh(key, cmp);
2428 }
2429
2430 void checkKeyBounds(K key, Comparator<? super K> cmp) {
2431 if (key == null)
2432 throw new NullPointerException();
2433 if (!inBounds(key, cmp))
2434 throw new IllegalArgumentException("key out of range");
2435 }
2436
2437 /**
2438 * Returns true if node key is less than upper bound of range.
2439 */
2440 boolean isBeforeEnd(ConcurrentSkipListMap.Node<K,V> n,
2441 Comparator<? super K> cmp) {
2442 if (n == null)
2443 return false;
2444 if (hi == null)
2445 return true;
2446 K k = n.key;
2447 if (k == null) // pass by markers and headers
2448 return true;
2449 int c = cpr(cmp, k, hi);
2450 return c < 0 || (c == 0 && hiInclusive);
2451 }
2452
2453 /**
2454 * Returns lowest node. This node might not be in range, so
2455 * most usages need to check bounds.
2456 */
2457 ConcurrentSkipListMap.Node<K,V> loNode(Comparator<? super K> cmp) {
2458 if (lo == null)
2459 return m.findFirst();
2460 else if (loInclusive)
2461 return m.findNear(lo, GT|EQ, cmp);
2462 else
2463 return m.findNear(lo, GT, cmp);
2464 }
2465
2466 /**
2467 * Returns highest node. This node might not be in range, so
2468 * most usages need to check bounds.
2469 */
2470 ConcurrentSkipListMap.Node<K,V> hiNode(Comparator<? super K> cmp) {
2471 if (hi == null)
2472 return m.findLast();
2473 else if (hiInclusive)
2474 return m.findNear(hi, LT|EQ, cmp);
2475 else
2476 return m.findNear(hi, LT, cmp);
2477 }
2478
2479 /**
2480 * Returns lowest absolute key (ignoring directionality).
2481 */
2482 K lowestKey() {
2483 Comparator<? super K> cmp = m.comparator;
2484 ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
2485 if (isBeforeEnd(n, cmp))
2486 return n.key;
2487 else
2488 throw new NoSuchElementException();
2489 }
2490
2491 /**
2492 * Returns highest absolute key (ignoring directionality).
2493 */
2494 K highestKey() {
2495 Comparator<? super K> cmp = m.comparator;
2496 ConcurrentSkipListMap.Node<K,V> n = hiNode(cmp);
2497 if (n != null) {
2498 K last = n.key;
2499 if (inBounds(last, cmp))
2500 return last;
2501 }
2502 throw new NoSuchElementException();
2503 }
2504
2505 Map.Entry<K,V> lowestEntry() {
2506 Comparator<? super K> cmp = m.comparator;
2507 for (;;) {
2508 ConcurrentSkipListMap.Node<K,V> n; V v;
2509 if ((n = loNode(cmp)) == null || !isBeforeEnd(n, cmp))
2510 return null;
2511 else if ((v = n.val) != null)
2512 return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
2513 }
2514 }
2515
2516 Map.Entry<K,V> highestEntry() {
2517 Comparator<? super K> cmp = m.comparator;
2518 for (;;) {
2519 ConcurrentSkipListMap.Node<K,V> n; V v;
2520 if ((n = hiNode(cmp)) == null || !inBounds(n.key, cmp))
2521 return null;
2522 else if ((v = n.val) != null)
2523 return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
2524 }
2525 }
2526
2527 Map.Entry<K,V> removeLowest() {
2528 Comparator<? super K> cmp = m.comparator;
2529 for (;;) {
2530 ConcurrentSkipListMap.Node<K,V> n; K k; V v;
2531 if ((n = loNode(cmp)) == null)
2532 return null;
2533 else if (!inBounds((k = n.key), cmp))
2534 return null;
2535 else if ((v = m.doRemove(k, null)) != null)
2536 return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2537 }
2538 }
2539
2540 Map.Entry<K,V> removeHighest() {
2541 Comparator<? super K> cmp = m.comparator;
2542 for (;;) {
2543 ConcurrentSkipListMap.Node<K,V> n; K k; V v;
2544 if ((n = hiNode(cmp)) == null)
2545 return null;
2546 else if (!inBounds((k = n.key), cmp))
2547 return null;
2548 else if ((v = m.doRemove(k, null)) != null)
2549 return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2550 }
2551 }
2552
2553 /**
2554 * Submap version of ConcurrentSkipListMap.findNearEntry.
2555 */
2556 Map.Entry<K,V> getNearEntry(K key, int rel) {
2557 Comparator<? super K> cmp = m.comparator;
2558 if (isDescending) { // adjust relation for direction
2559 if ((rel & LT) == 0)
2560 rel |= LT;
2561 else
2562 rel &= ~LT;
2563 }
2564 if (tooLow(key, cmp))
2565 return ((rel & LT) != 0) ? null : lowestEntry();
2566 if (tooHigh(key, cmp))
2567 return ((rel & LT) != 0) ? highestEntry() : null;
2568 AbstractMap.SimpleImmutableEntry<K,V> e =
2569 m.findNearEntry(key, rel, cmp);
2570 if (e == null || !inBounds(e.getKey(), cmp))
2571 return null;
2572 else
2573 return e;
2574 }
2575
2576 // Almost the same as getNearEntry, except for keys
2577 K getNearKey(K key, int rel) {
2578 Comparator<? super K> cmp = m.comparator;
2579 if (isDescending) { // adjust relation for direction
2580 if ((rel & LT) == 0)
2581 rel |= LT;
2582 else
2583 rel &= ~LT;
2584 }
2585 if (tooLow(key, cmp)) {
2586 if ((rel & LT) == 0) {
2587 ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
2588 if (isBeforeEnd(n, cmp))
2589 return n.key;
2590 }
2591 return null;
2592 }
2593 if (tooHigh(key, cmp)) {
2594 if ((rel & LT) != 0) {
2595 ConcurrentSkipListMap.Node<K,V> n = hiNode(cmp);
2596 if (n != null) {
2597 K last = n.key;
2598 if (inBounds(last, cmp))
2599 return last;
2600 }
2601 }
2602 return null;
2603 }
2604 for (;;) {
2605 Node<K,V> n = m.findNear(key, rel, cmp);
2606 if (n == null || !inBounds(n.key, cmp))
2607 return null;
2608 if (n.val != null)
2609 return n.key;
2610 }
2611 }
2612
2613 /* ---------------- Map API methods -------------- */
2614
2615 public boolean containsKey(Object key) {
2616 if (key == null) throw new NullPointerException();
2617 return inBounds(key, m.comparator) && m.containsKey(key);
2618 }
2619
2620 public V get(Object key) {
2621 if (key == null) throw new NullPointerException();
2622 return (!inBounds(key, m.comparator)) ? null : m.get(key);
2623 }
2624
2625 public V put(K key, V value) {
2626 checkKeyBounds(key, m.comparator);
2627 return m.put(key, value);
2628 }
2629
2630 public V remove(Object key) {
2631 return (!inBounds(key, m.comparator)) ? null : m.remove(key);
2632 }
2633
2634 public int size() {
2635 Comparator<? super K> cmp = m.comparator;
2636 long count = 0;
2637 for (ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
2638 isBeforeEnd(n, cmp);
2639 n = n.next) {
2640 if (n.val != null)
2641 ++count;
2642 }
2643 return count >= Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)count;
2644 }
2645
2646 public boolean isEmpty() {
2647 Comparator<? super K> cmp = m.comparator;
2648 return !isBeforeEnd(loNode(cmp), cmp);
2649 }
2650
2651 public boolean containsValue(Object value) {
2652 if (value == null)
2653 throw new NullPointerException();
2654 Comparator<? super K> cmp = m.comparator;
2655 for (ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
2656 isBeforeEnd(n, cmp);
2657 n = n.next) {
2658 V v = n.val;
2659 if (v != null && value.equals(v))
2660 return true;
2661 }
2662 return false;
2663 }
2664
2665 public void clear() {
2666 Comparator<? super K> cmp = m.comparator;
2667 for (ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
2668 isBeforeEnd(n, cmp);
2669 n = n.next) {
2670 if (n.val != null)
2671 m.remove(n.key);
2672 }
2673 }
2674
2675 /* ---------------- ConcurrentMap API methods -------------- */
2676
2677 public V putIfAbsent(K key, V value) {
2678 checkKeyBounds(key, m.comparator);
2679 return m.putIfAbsent(key, value);
2680 }
2681
2682 public boolean remove(Object key, Object value) {
2683 return inBounds(key, m.comparator) && m.remove(key, value);
2684 }
2685
2686 public boolean replace(K key, V oldValue, V newValue) {
2687 checkKeyBounds(key, m.comparator);
2688 return m.replace(key, oldValue, newValue);
2689 }
2690
2691 public V replace(K key, V value) {
2692 checkKeyBounds(key, m.comparator);
2693 return m.replace(key, value);
2694 }
2695
2696 /* ---------------- SortedMap API methods -------------- */
2697
2698 public Comparator<? super K> comparator() {
2699 Comparator<? super K> cmp = m.comparator();
2700 if (isDescending)
2701 return Collections.reverseOrder(cmp);
2702 else
2703 return cmp;
2704 }
2705
2706 /**
2707 * Utility to create submaps, where given bounds override
2708 * unbounded(null) ones and/or are checked against bounded ones.
2709 */
2710 SubMap<K,V> newSubMap(K fromKey, boolean fromInclusive,
2711 K toKey, boolean toInclusive) {
2712 Comparator<? super K> cmp = m.comparator;
2713 if (isDescending) { // flip senses
2714 K tk = fromKey;
2715 fromKey = toKey;
2716 toKey = tk;
2717 boolean ti = fromInclusive;
2718 fromInclusive = toInclusive;
2719 toInclusive = ti;
2720 }
2721 if (lo != null) {
2722 if (fromKey == null) {
2723 fromKey = lo;
2724 fromInclusive = loInclusive;
2725 }
2726 else {
2727 int c = cpr(cmp, fromKey, lo);
2728 if (c < 0 || (c == 0 && !loInclusive && fromInclusive))
2729 throw new IllegalArgumentException("key out of range");
2730 }
2731 }
2732 if (hi != null) {
2733 if (toKey == null) {
2734 toKey = hi;
2735 toInclusive = hiInclusive;
2736 }
2737 else {
2738 int c = cpr(cmp, toKey, hi);
2739 if (c > 0 || (c == 0 && !hiInclusive && toInclusive))
2740 throw new IllegalArgumentException("key out of range");
2741 }
2742 }
2743 return new SubMap<K,V>(m, fromKey, fromInclusive,
2744 toKey, toInclusive, isDescending);
2745 }
2746
2747 public SubMap<K,V> subMap(K fromKey, boolean fromInclusive,
2748 K toKey, boolean toInclusive) {
2749 if (fromKey == null || toKey == null)
2750 throw new NullPointerException();
2751 return newSubMap(fromKey, fromInclusive, toKey, toInclusive);
2752 }
2753
2754 public SubMap<K,V> headMap(K toKey, boolean inclusive) {
2755 if (toKey == null)
2756 throw new NullPointerException();
2757 return newSubMap(null, false, toKey, inclusive);
2758 }
2759
2760 public SubMap<K,V> tailMap(K fromKey, boolean inclusive) {
2761 if (fromKey == null)
2762 throw new NullPointerException();
2763 return newSubMap(fromKey, inclusive, null, false);
2764 }
2765
2766 public SubMap<K,V> subMap(K fromKey, K toKey) {
2767 return subMap(fromKey, true, toKey, false);
2768 }
2769
2770 public SubMap<K,V> headMap(K toKey) {
2771 return headMap(toKey, false);
2772 }
2773
2774 public SubMap<K,V> tailMap(K fromKey) {
2775 return tailMap(fromKey, true);
2776 }
2777
2778 public SubMap<K,V> descendingMap() {
2779 return new SubMap<K,V>(m, lo, loInclusive,
2780 hi, hiInclusive, !isDescending);
2781 }
2782
2783 /* ---------------- Relational methods -------------- */
2784
2785 public Map.Entry<K,V> ceilingEntry(K key) {
2786 return getNearEntry(key, GT|EQ);
2787 }
2788
2789 public K ceilingKey(K key) {
2790 return getNearKey(key, GT|EQ);
2791 }
2792
2793 public Map.Entry<K,V> lowerEntry(K key) {
2794 return getNearEntry(key, LT);
2795 }
2796
2797 public K lowerKey(K key) {
2798 return getNearKey(key, LT);
2799 }
2800
2801 public Map.Entry<K,V> floorEntry(K key) {
2802 return getNearEntry(key, LT|EQ);
2803 }
2804
2805 public K floorKey(K key) {
2806 return getNearKey(key, LT|EQ);
2807 }
2808
2809 public Map.Entry<K,V> higherEntry(K key) {
2810 return getNearEntry(key, GT);
2811 }
2812
2813 public K higherKey(K key) {
2814 return getNearKey(key, GT);
2815 }
2816
2817 public K firstKey() {
2818 return isDescending ? highestKey() : lowestKey();
2819 }
2820
2821 public K lastKey() {
2822 return isDescending ? lowestKey() : highestKey();
2823 }
2824
2825 public Map.Entry<K,V> firstEntry() {
2826 return isDescending ? highestEntry() : lowestEntry();
2827 }
2828
2829 public Map.Entry<K,V> lastEntry() {
2830 return isDescending ? lowestEntry() : highestEntry();
2831 }
2832
2833 public Map.Entry<K,V> pollFirstEntry() {
2834 return isDescending ? removeHighest() : removeLowest();
2835 }
2836
2837 public Map.Entry<K,V> pollLastEntry() {
2838 return isDescending ? removeLowest() : removeHighest();
2839 }
2840
2841 /* ---------------- Submap Views -------------- */
2842
2843 public NavigableSet<K> keySet() {
2844 KeySet<K,V> ks;
2845 if ((ks = keySetView) != null) return ks;
2846 return keySetView = new KeySet<>(this);
2847 }
2848
2849 public NavigableSet<K> navigableKeySet() {
2850 KeySet<K,V> ks;
2851 if ((ks = keySetView) != null) return ks;
2852 return keySetView = new KeySet<>(this);
2853 }
2854
2855 public Collection<V> values() {
2856 Values<K,V> vs;
2857 if ((vs = valuesView) != null) return vs;
2858 return valuesView = new Values<>(this);
2859 }
2860
2861 public Set<Map.Entry<K,V>> entrySet() {
2862 EntrySet<K,V> es;
2863 if ((es = entrySetView) != null) return es;
2864 return entrySetView = new EntrySet<K,V>(this);
2865 }
2866
2867 public NavigableSet<K> descendingKeySet() {
2868 return descendingMap().navigableKeySet();
2869 }
2870
2871 /**
2872 * Variant of main Iter class to traverse through submaps.
2873 * Also serves as back-up Spliterator for views.
2874 */
2875 abstract class SubMapIter<T> implements Iterator<T>, Spliterator<T> {
2876 /** the last node returned by next() */
2877 Node<K,V> lastReturned;
2878 /** the next node to return from next(); */
2879 Node<K,V> next;
2880 /** Cache of next value field to maintain weak consistency */
2881 V nextValue;
2882
2883 SubMapIter() {
2884 VarHandle.acquireFence();
2885 Comparator<? super K> cmp = m.comparator;
2886 for (;;) {
2887 next = isDescending ? hiNode(cmp) : loNode(cmp);
2888 if (next == null)
2889 break;
2890 V x = next.val;
2891 if (x != null) {
2892 if (! inBounds(next.key, cmp))
2893 next = null;
2894 else
2895 nextValue = x;
2896 break;
2897 }
2898 }
2899 }
2900
2901 public final boolean hasNext() {
2902 return next != null;
2903 }
2904
2905 final void advance() {
2906 if (next == null)
2907 throw new NoSuchElementException();
2908 lastReturned = next;
2909 if (isDescending)
2910 descend();
2911 else
2912 ascend();
2913 }
2914
2915 private void ascend() {
2916 Comparator<? super K> cmp = m.comparator;
2917 for (;;) {
2918 next = next.next;
2919 if (next == null)
2920 break;
2921 V x = next.val;
2922 if (x != null) {
2923 if (tooHigh(next.key, cmp))
2924 next = null;
2925 else
2926 nextValue = x;
2927 break;
2928 }
2929 }
2930 }
2931
2932 private void descend() {
2933 Comparator<? super K> cmp = m.comparator;
2934 for (;;) {
2935 next = m.findNear(lastReturned.key, LT, cmp);
2936 if (next == null)
2937 break;
2938 V x = next.val;
2939 if (x != null) {
2940 if (tooLow(next.key, cmp))
2941 next = null;
2942 else
2943 nextValue = x;
2944 break;
2945 }
2946 }
2947 }
2948
2949 public void remove() {
2950 Node<K,V> l = lastReturned;
2951 if (l == null)
2952 throw new IllegalStateException();
2953 m.remove(l.key);
2954 lastReturned = null;
2955 }
2956
2957 public Spliterator<T> trySplit() {
2958 return null;
2959 }
2960
2961 public boolean tryAdvance(Consumer<? super T> action) {
2962 if (hasNext()) {
2963 action.accept(next());
2964 return true;
2965 }
2966 return false;
2967 }
2968
2969 public void forEachRemaining(Consumer<? super T> action) {
2970 while (hasNext())
2971 action.accept(next());
2972 }
2973
2974 public long estimateSize() {
2975 return Long.MAX_VALUE;
2976 }
2977
2978 }
2979
2980 final class SubMapValueIterator extends SubMapIter<V> {
2981 public V next() {
2982 V v = nextValue;
2983 advance();
2984 return v;
2985 }
2986 public int characteristics() {
2987 return 0;
2988 }
2989 }
2990
2991 final class SubMapKeyIterator extends SubMapIter<K> {
2992 public K next() {
2993 Node<K,V> n = next;
2994 advance();
2995 return n.key;
2996 }
2997 public int characteristics() {
2998 return Spliterator.DISTINCT | Spliterator.ORDERED |
2999 Spliterator.SORTED;
3000 }
3001 public final Comparator<? super K> getComparator() {
3002 return SubMap.this.comparator();
3003 }
3004 }
3005
3006 final class SubMapEntryIterator extends SubMapIter<Map.Entry<K,V>> {
3007 public Map.Entry<K,V> next() {
3008 Node<K,V> n = next;
3009 V v = nextValue;
3010 advance();
3011 return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
3012 }
3013 public int characteristics() {
3014 return Spliterator.DISTINCT;
3015 }
3016 }
3017 }
3018
3019 // default Map method overrides
3020
3021 public void forEach(BiConsumer<? super K, ? super V> action) {
3022 if (action == null) throw new NullPointerException();
3023 Node<K,V> b, n; V v;
3024 if ((b = baseHead()) != null) {
3025 while ((n = b.next) != null) {
3026 if ((v = n.val) != null)
3027 action.accept(n.key, v);
3028 b = n;
3029 }
3030 }
3031 }
3032
3033 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
3034 if (function == null) throw new NullPointerException();
3035 Node<K,V> b, n; V v;
3036 if ((b = baseHead()) != null) {
3037 while ((n = b.next) != null) {
3038 while ((v = n.val) != null) {
3039 V r = function.apply(n.key, v);
3040 if (r == null) throw new NullPointerException();
3041 if (VAL.compareAndSet(n, v, r))
3042 break;
3043 }
3044 b = n;
3045 }
3046 }
3047 }
3048
3049 /**
3050 * Helper method for EntrySet.removeIf.
3051 */
3052 boolean removeEntryIf(Predicate<? super Entry<K,V>> function) {
3053 if (function == null) throw new NullPointerException();
3054 boolean removed = false;
3055 Node<K,V> b, n; V v;
3056 if ((b = baseHead()) != null) {
3057 while ((n = b.next) != null) {
3058 if ((v = n.val) != null) {
3059 K k = n.key;
3060 Map.Entry<K,V> e = new AbstractMap.SimpleImmutableEntry<>(k, v);
3061 if (function.test(e) && remove(k, v))
3062 removed = true;
3063 }
3064 b = n;
3065 }
3066 }
3067 return removed;
3068 }
3069
3070 /**
3071 * Helper method for Values.removeIf.
3072 */
3073 boolean removeValueIf(Predicate<? super V> function) {
3074 if (function == null) throw new NullPointerException();
3075 boolean removed = false;
3076 Node<K,V> b, n; V v;
3077 if ((b = baseHead()) != null) {
3078 while ((n = b.next) != null) {
3079 if ((v = n.val) != null && function.test(v) && remove(n.key, v))
3080 removed = true;
3081 b = n;
3082 }
3083 }
3084 return removed;
3085 }
3086
3087 /**
3088 * Base class providing common structure for Spliterators.
3089 * (Although not all that much common functionality; as usual for
3090 * view classes, details annoyingly vary in key, value, and entry
3091 * subclasses in ways that are not worth abstracting out for
3092 * internal classes.)
3093 *
3094 * The basic split strategy is to recursively descend from top
3095 * level, row by row, descending to next row when either split
3096 * off, or the end of row is encountered. Control of the number of
3097 * splits relies on some statistical estimation: The expected
3098 * remaining number of elements of a skip list when advancing
3099 * either across or down decreases by about 25%.
3100 */
3101 abstract static class CSLMSpliterator<K,V> {
3102 final Comparator<? super K> comparator;
3103 final K fence; // exclusive upper bound for keys, or null if to end
3104 Index<K,V> row; // the level to split out
3105 Node<K,V> current; // current traversal node; initialize at origin
3106 long est; // size estimate
3107 CSLMSpliterator(Comparator<? super K> comparator, Index<K,V> row,
3108 Node<K,V> origin, K fence, long est) {
3109 this.comparator = comparator; this.row = row;
3110 this.current = origin; this.fence = fence; this.est = est;
3111 }
3112
3113 public final long estimateSize() { return est; }
3114 }
3115
3116 static final class KeySpliterator<K,V> extends CSLMSpliterator<K,V>
3117 implements Spliterator<K> {
3118 KeySpliterator(Comparator<? super K> comparator, Index<K,V> row,
3119 Node<K,V> origin, K fence, long est) {
3120 super(comparator, row, origin, fence, est);
3121 }
3122
3123 public KeySpliterator<K,V> trySplit() {
3124 Node<K,V> e; K ek;
3125 Comparator<? super K> cmp = comparator;
3126 K f = fence;
3127 if ((e = current) != null && (ek = e.key) != null) {
3128 for (Index<K,V> q = row; q != null; q = row = q.down) {
3129 Index<K,V> s; Node<K,V> b, n; K sk;
3130 if ((s = q.right) != null && (b = s.node) != null &&
3131 (n = b.next) != null && n.val != null &&
3132 (sk = n.key) != null && cpr(cmp, sk, ek) > 0 &&
3133 (f == null || cpr(cmp, sk, f) < 0)) {
3134 current = n;
3135 Index<K,V> r = q.down;
3136 row = (s.right != null) ? s : s.down;
3137 est -= est >>> 2;
3138 return new KeySpliterator<K,V>(cmp, r, e, sk, est);
3139 }
3140 }
3141 }
3142 return null;
3143 }
3144
3145 public void forEachRemaining(Consumer<? super K> action) {
3146 if (action == null) throw new NullPointerException();
3147 Comparator<? super K> cmp = comparator;
3148 K f = fence;
3149 Node<K,V> e = current;
3150 current = null;
3151 for (; e != null; e = e.next) {
3152 K k;
3153 if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0)
3154 break;
3155 if (e.val != null)
3156 action.accept(k);
3157 }
3158 }
3159
3160 public boolean tryAdvance(Consumer<? super K> action) {
3161 if (action == null) throw new NullPointerException();
3162 Comparator<? super K> cmp = comparator;
3163 K f = fence;
3164 Node<K,V> e = current;
3165 for (; e != null; e = e.next) {
3166 K k;
3167 if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) {
3168 e = null;
3169 break;
3170 }
3171 if (e.val != null) {
3172 current = e.next;
3173 action.accept(k);
3174 return true;
3175 }
3176 }
3177 current = e;
3178 return false;
3179 }
3180
3181 public int characteristics() {
3182 return Spliterator.DISTINCT | Spliterator.SORTED |
3183 Spliterator.ORDERED | Spliterator.CONCURRENT |
3184 Spliterator.NONNULL;
3185 }
3186
3187 public final Comparator<? super K> getComparator() {
3188 return comparator;
3189 }
3190 }
3191 // factory method for KeySpliterator
3192 final KeySpliterator<K,V> keySpliterator() {
3193 Index<K,V> h; Node<K,V> n; long est;
3194 VarHandle.acquireFence();
3195 if ((h = head) == null) {
3196 n = null;
3197 est = 0L;
3198 }
3199 else {
3200 n = h.node;
3201 est = getAdderCount();
3202 }
3203 return new KeySpliterator<K,V>(comparator, h, n, null, est);
3204 }
3205
3206 static final class ValueSpliterator<K,V> extends CSLMSpliterator<K,V>
3207 implements Spliterator<V> {
3208 ValueSpliterator(Comparator<? super K> comparator, Index<K,V> row,
3209 Node<K,V> origin, K fence, long est) {
3210 super(comparator, row, origin, fence, est);
3211 }
3212
3213 public ValueSpliterator<K,V> trySplit() {
3214 Node<K,V> e; K ek;
3215 Comparator<? super K> cmp = comparator;
3216 K f = fence;
3217 if ((e = current) != null && (ek = e.key) != null) {
3218 for (Index<K,V> q = row; q != null; q = row = q.down) {
3219 Index<K,V> s; Node<K,V> b, n; K sk;
3220 if ((s = q.right) != null && (b = s.node) != null &&
3221 (n = b.next) != null && n.val != null &&
3222 (sk = n.key) != null && cpr(cmp, sk, ek) > 0 &&
3223 (f == null || cpr(cmp, sk, f) < 0)) {
3224 current = n;
3225 Index<K,V> r = q.down;
3226 row = (s.right != null) ? s : s.down;
3227 est -= est >>> 2;
3228 return new ValueSpliterator<K,V>(cmp, r, e, sk, est);
3229 }
3230 }
3231 }
3232 return null;
3233 }
3234
3235 public void forEachRemaining(Consumer<? super V> action) {
3236 if (action == null) throw new NullPointerException();
3237 Comparator<? super K> cmp = comparator;
3238 K f = fence;
3239 Node<K,V> e = current;
3240 current = null;
3241 for (; e != null; e = e.next) {
3242 K k; V v;
3243 if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0)
3244 break;
3245 if ((v = e.val) != null)
3246 action.accept(v);
3247 }
3248 }
3249
3250 public boolean tryAdvance(Consumer<? super V> action) {
3251 if (action == null) throw new NullPointerException();
3252 Comparator<? super K> cmp = comparator;
3253 K f = fence;
3254 Node<K,V> e = current;
3255 for (; e != null; e = e.next) {
3256 K k; V v;
3257 if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) {
3258 e = null;
3259 break;
3260 }
3261 if ((v = e.val) != null) {
3262 current = e.next;
3263 action.accept(v);
3264 return true;
3265 }
3266 }
3267 current = e;
3268 return false;
3269 }
3270
3271 public int characteristics() {
3272 return Spliterator.CONCURRENT | Spliterator.ORDERED |
3273 Spliterator.NONNULL;
3274 }
3275 }
3276
3277 // Almost the same as keySpliterator()
3278 final ValueSpliterator<K,V> valueSpliterator() {
3279 Index<K,V> h; Node<K,V> n; long est;
3280 VarHandle.acquireFence();
3281 if ((h = head) == null) {
3282 n = null;
3283 est = 0L;
3284 }
3285 else {
3286 n = h.node;
3287 est = getAdderCount();
3288 }
3289 return new ValueSpliterator<K,V>(comparator, h, n, null, est);
3290 }
3291
3292 static final class EntrySpliterator<K,V> extends CSLMSpliterator<K,V>
3293 implements Spliterator<Map.Entry<K,V>> {
3294 EntrySpliterator(Comparator<? super K> comparator, Index<K,V> row,
3295 Node<K,V> origin, K fence, long est) {
3296 super(comparator, row, origin, fence, est);
3297 }
3298
3299 public EntrySpliterator<K,V> trySplit() {
3300 Node<K,V> e; K ek;
3301 Comparator<? super K> cmp = comparator;
3302 K f = fence;
3303 if ((e = current) != null && (ek = e.key) != null) {
3304 for (Index<K,V> q = row; q != null; q = row = q.down) {
3305 Index<K,V> s; Node<K,V> b, n; K sk;
3306 if ((s = q.right) != null && (b = s.node) != null &&
3307 (n = b.next) != null && n.val != null &&
3308 (sk = n.key) != null && cpr(cmp, sk, ek) > 0 &&
3309 (f == null || cpr(cmp, sk, f) < 0)) {
3310 current = n;
3311 Index<K,V> r = q.down;
3312 row = (s.right != null) ? s : s.down;
3313 est -= est >>> 2;
3314 return new EntrySpliterator<K,V>(cmp, r, e, sk, est);
3315 }
3316 }
3317 }
3318 return null;
3319 }
3320
3321 public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
3322 if (action == null) throw new NullPointerException();
3323 Comparator<? super K> cmp = comparator;
3324 K f = fence;
3325 Node<K,V> e = current;
3326 current = null;
3327 for (; e != null; e = e.next) {
3328 K k; V v;
3329 if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0)
3330 break;
3331 if ((v = e.val) != null) {
3332 action.accept
3333 (new AbstractMap.SimpleImmutableEntry<K,V>(k, v));
3334 }
3335 }
3336 }
3337
3338 public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
3339 if (action == null) throw new NullPointerException();
3340 Comparator<? super K> cmp = comparator;
3341 K f = fence;
3342 Node<K,V> e = current;
3343 for (; e != null; e = e.next) {
3344 K k; V v;
3345 if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) {
3346 e = null;
3347 break;
3348 }
3349 if ((v = e.val) != null) {
3350 current = e.next;
3351 action.accept
3352 (new AbstractMap.SimpleImmutableEntry<K,V>(k, v));
3353 return true;
3354 }
3355 }
3356 current = e;
3357 return false;
3358 }
3359
3360 public int characteristics() {
3361 return Spliterator.DISTINCT | Spliterator.SORTED |
3362 Spliterator.ORDERED | Spliterator.CONCURRENT |
3363 Spliterator.NONNULL;
3364 }
3365
3366 public final Comparator<Map.Entry<K,V>> getComparator() {
3367 // Adapt or create a key-based comparator
3368 if (comparator != null) {
3369 return Map.Entry.comparingByKey(comparator);
3370 }
3371 else {
3372 return (Comparator<Map.Entry<K,V>> & Serializable) (e1, e2) -> {
3373 @SuppressWarnings("unchecked")
3374 Comparable<? super K> k1 = (Comparable<? super K>) e1.getKey();
3375 return k1.compareTo(e2.getKey());
3376 };
3377 }
3378 }
3379 }
3380
3381 // Almost the same as keySpliterator()
3382 final EntrySpliterator<K,V> entrySpliterator() {
3383 Index<K,V> h; Node<K,V> n; long est;
3384 VarHandle.acquireFence();
3385 if ((h = head) == null) {
3386 n = null;
3387 est = 0L;
3388 }
3389 else {
3390 n = h.node;
3391 est = getAdderCount();
3392 }
3393 return new EntrySpliterator<K,V>(comparator, h, n, null, est);
3394 }
3395
3396 // VarHandle mechanics
3397 private static final VarHandle HEAD;
3398 private static final VarHandle ADDER;
3399 private static final VarHandle NEXT;
3400 private static final VarHandle VAL;
3401 private static final VarHandle RIGHT;
3402 static {
3403 try {
3404 MethodHandles.Lookup l = MethodHandles.lookup();
3405 HEAD = l.findVarHandle(ConcurrentSkipListMap.class, "head",
3406 Index.class);
3407 ADDER = l.findVarHandle(ConcurrentSkipListMap.class, "adder",
3408 LongAdder.class);
3409 NEXT = l.findVarHandle(Node.class, "next", Node.class);
3410 VAL = l.findVarHandle(Node.class, "val", Object.class);
3411 RIGHT = l.findVarHandle(Index.class, "right", Index.class);
3412 } catch (ReflectiveOperationException e) {
3413 throw new ExceptionInInitializerError(e);
3414 }
3415 }
3416 }
3417