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.buildFromSorted(this);
1133 return clone;
1134 } catch (CloneNotSupportedException e) {
1135 throw new InternalError();
1136 }
1137 }
1138
1139 /**
1140 * Streamlined bulk insertion to initialize from elements of
1141 * given sorted map. Call only from constructor or clone
1142 * method.
1143 */
1144 private void buildFromSorted(SortedMap<K, ? extends V> map) {
1145 if (map == null)
1146 throw new NullPointerException();
1147 Iterator<? extends Map.Entry<? extends K, ? extends V>> it =
1148 map.entrySet().iterator();
1149
1150 /*
1151 * Add equally spaced indices at log intervals, using the bits
1152 * of count during insertion. The maximum possible resulting
1153 * level is less than the number of bits in a long (64). The
1154 * preds array tracks the current rightmost node at each
1155 * level.
1156 */
1157 @SuppressWarnings("unchecked")
1158 Index<K,V>[] preds = (Index<K,V>[])new Index<?,?>[64];
1159 Node<K,V> bp = new Node<K,V>(null, null, null);
1160 Index<K,V> h = preds[0] = new Index<K,V>(bp, null, null);
1161 long count = 0;
1162
1163 while (it.hasNext()) {
1164 Map.Entry<? extends K, ? extends V> e = it.next();
1165 K k = e.getKey();
1166 V v = e.getValue();
1167 if (k == null || v == null)
1168 throw new NullPointerException();
1169 Node<K,V> z = new Node<K,V>(k, v, null);
1170 bp = bp.next = z;
1171 if ((++count & 3L) == 0L) {
1172 long m = count >>> 2;
1173 int i = 0;
1174 Index<K,V> idx = null, q;
1175 do {
1176 idx = new Index<K,V>(z, idx, null);
1177 if ((q = preds[i]) == null)
1178 preds[i] = h = new Index<K,V>(h.node, h, idx);
1179 else
1180 preds[i] = q.right = idx;
1181 } while (++i < preds.length && ((m >>>= 1) & 1L) != 0L);
1182 }
1183 }
1184 if (count != 0L) {
1185 VarHandle.releaseFence(); // emulate volatile stores
1186 addCount(count);
1187 head = h;
1188 VarHandle.fullFence();
1189 }
1190 }
1191
1192 /* ---------------- Serialization -------------- */
1193
1194 /**
1195 * Saves this map to a stream (that is, serializes it).
1196 *
1197 * @param s the stream
1198 * @throws java.io.IOException if an I/O error occurs
1199 * @serialData The key (Object) and value (Object) for each
1200 * key-value mapping represented by the map, followed by
1201 * {@code null}. The key-value mappings are emitted in key-order
1202 * (as determined by the Comparator, or by the keys' natural
1203 * ordering if no Comparator).
1204 */
1205 private void writeObject(java.io.ObjectOutputStream s)
1206 throws java.io.IOException {
1207 // Write out the Comparator and any hidden stuff
1208 s.defaultWriteObject();
1209
1210 // Write out keys and values (alternating)
1211 Node<K,V> b, n; V v;
1212 if ((b = baseHead()) != null) {
1213 while ((n = b.next) != null) {
1214 if ((v = n.val) != null) {
1215 s.writeObject(n.key);
1216 s.writeObject(v);
1217 }
1218 b = n;
1219 }
1220 }
1221 s.writeObject(null);
1222 }
1223
1224 /**
1225 * Reconstitutes this map from a stream (that is, deserializes it).
1226 * @param s the stream
1227 * @throws ClassNotFoundException if the class of a serialized object
1228 * could not be found
1229 * @throws java.io.IOException if an I/O error occurs
1230 */
1231 @SuppressWarnings("unchecked")
1232 private void readObject(final java.io.ObjectInputStream s)
1233 throws java.io.IOException, ClassNotFoundException {
1234 // Read in the Comparator and any hidden stuff
1235 s.defaultReadObject();
1236
1237 // Same idea as buildFromSorted
1238 @SuppressWarnings("unchecked")
1239 Index<K,V>[] preds = (Index<K,V>[])new Index<?,?>[64];
1240 Node<K,V> bp = new Node<K,V>(null, null, null);
1241 Index<K,V> h = preds[0] = new Index<K,V>(bp, null, null);
1242 Comparator<? super K> cmp = comparator;
1243 K prevKey = null;
1244 long count = 0;
1245
1246 for (;;) {
1247 K k = (K)s.readObject();
1248 if (k == null)
1249 break;
1250 V v = (V)s.readObject();
1251 if (v == null)
1252 throw new NullPointerException();
1253 if (prevKey != null && cpr(cmp, prevKey, k) > 0)
1254 throw new IllegalStateException("out of order");
1255 prevKey = k;
1256 Node<K,V> z = new Node<K,V>(k, v, null);
1257 bp = bp.next = z;
1258 if ((++count & 3L) == 0L) {
1259 long m = count >>> 2;
1260 int i = 0;
1261 Index<K,V> idx = null, q;
1262 do {
1263 idx = new Index<K,V>(z, idx, null);
1264 if ((q = preds[i]) == null)
1265 preds[i] = h = new Index<K,V>(h.node, h, idx);
1266 else
1267 preds[i] = q.right = idx;
1268 } while (++i < preds.length && ((m >>>= 1) & 1L) != 0L);
1269 }
1270 }
1271 if (count != 0L) {
1272 VarHandle.releaseFence();
1273 addCount(count);
1274 head = h;
1275 VarHandle.fullFence();
1276 }
1277 }
1278
1279 /* ------ Map API methods ------ */
1280
1281 /**
1282 * Returns {@code true} if this map contains a mapping for the specified
1283 * key.
1284 *
1285 * @param key key whose presence in this map is to be tested
1286 * @return {@code true} if this map contains a mapping for the specified key
1287 * @throws ClassCastException if the specified key cannot be compared
1288 * with the keys currently in the map
1289 * @throws NullPointerException if the specified key is null
1290 */
1291 public boolean containsKey(Object key) {
1292 return doGet(key) != null;
1293 }
1294
1295 /**
1296 * Returns the value to which the specified key is mapped,
1297 * or {@code null} if this map contains no mapping for the key.
1298 *
1299 * <p>More formally, if this map contains a mapping from a key
1300 * {@code k} to a value {@code v} such that {@code key} compares
1301 * equal to {@code k} according to the map's ordering, then this
1302 * method returns {@code v}; otherwise it returns {@code null}.
1303 * (There can be at most one such mapping.)
1304 *
1305 * @throws ClassCastException if the specified key cannot be compared
1306 * with the keys currently in the map
1307 * @throws NullPointerException if the specified key is null
1308 */
1309 public V get(Object key) {
1310 return doGet(key);
1311 }
1312
1313 /**
1314 * Returns the value to which the specified key is mapped,
1315 * or the given defaultValue if this map contains no mapping for the key.
1316 *
1317 * @param key the key
1318 * @param defaultValue the value to return if this map contains
1319 * no mapping for the given key
1320 * @return the mapping for the key, if present; else the defaultValue
1321 * @throws NullPointerException if the specified key is null
1322 * @since 1.8
1323 */
1324 public V getOrDefault(Object key, V defaultValue) {
1325 V v;
1326 return (v = doGet(key)) == null ? defaultValue : v;
1327 }
1328
1329 /**
1330 * Associates the specified value with the specified key in this map.
1331 * If the map previously contained a mapping for the key, the old
1332 * value is replaced.
1333 *
1334 * @param key key with which the specified value is to be associated
1335 * @param value value to be associated with the specified key
1336 * @return the previous value associated with the specified key, or
1337 * {@code null} if there was no mapping for the key
1338 * @throws ClassCastException if the specified key cannot be compared
1339 * with the keys currently in the map
1340 * @throws NullPointerException if the specified key or value is null
1341 */
1342 public V put(K key, V value) {
1343 if (value == null)
1344 throw new NullPointerException();
1345 return doPut(key, value, false);
1346 }
1347
1348 /**
1349 * Removes the mapping for the specified key from this map if present.
1350 *
1351 * @param key key for which mapping should be removed
1352 * @return the previous value associated with the specified key, or
1353 * {@code null} if there was no mapping for the key
1354 * @throws ClassCastException if the specified key cannot be compared
1355 * with the keys currently in the map
1356 * @throws NullPointerException if the specified key is null
1357 */
1358 public V remove(Object key) {
1359 return doRemove(key, null);
1360 }
1361
1362 /**
1363 * Returns {@code true} if this map maps one or more keys to the
1364 * specified value. This operation requires time linear in the
1365 * map size. Additionally, it is possible for the map to change
1366 * during execution of this method, in which case the returned
1367 * result may be inaccurate.
1368 *
1369 * @param value value whose presence in this map is to be tested
1370 * @return {@code true} if a mapping to {@code value} exists;
1371 * {@code false} otherwise
1372 * @throws NullPointerException if the specified value is null
1373 */
1374 public boolean containsValue(Object value) {
1375 if (value == null)
1376 throw new NullPointerException();
1377 Node<K,V> b, n; V v;
1378 if ((b = baseHead()) != null) {
1379 while ((n = b.next) != null) {
1380 if ((v = n.val) != null && value.equals(v))
1381 return true;
1382 else
1383 b = n;
1384 }
1385 }
1386 return false;
1387 }
1388
1389 /**
1390 * {@inheritDoc}
1391 */
1392 public int size() {
1393 long c;
1394 return ((baseHead() == null) ? 0 :
1395 ((c = getAdderCount()) >= Integer.MAX_VALUE) ?
1396 Integer.MAX_VALUE : (int) c);
1397 }
1398
1399 /**
1400 * {@inheritDoc}
1401 */
1402 public boolean isEmpty() {
1403 return findFirst() == null;
1404 }
1405
1406 /**
1407 * Removes all of the mappings from this map.
1408 */
1409 public void clear() {
1410 Index<K,V> h, r, d; Node<K,V> b;
1411 VarHandle.acquireFence();
1412 while ((h = head) != null) {
1413 if ((r = h.right) != null) // remove indices
1414 RIGHT.compareAndSet(h, r, null);
1415 else if ((d = h.down) != null) // remove levels
1416 HEAD.compareAndSet(this, h, d);
1417 else {
1418 long count = 0L;
1419 if ((b = h.node) != null) { // remove nodes
1420 Node<K,V> n; V v;
1421 while ((n = b.next) != null) {
1422 if ((v = n.val) != null &&
1423 VAL.compareAndSet(n, v, null)) {
1424 --count;
1425 v = null;
1426 }
1427 if (v == null)
1428 unlinkNode(b, n);
1429 }
1430 }
1431 if (count != 0L)
1432 addCount(count);
1433 else
1434 break;
1435 }
1436 }
1437 }
1438
1439 /**
1440 * If the specified key is not already associated with a value,
1441 * attempts to compute its value using the given mapping function
1442 * and enters it into this map unless {@code null}. The function
1443 * is <em>NOT</em> guaranteed to be applied once atomically only
1444 * if the value is not present.
1445 *
1446 * @param key key with which the specified value is to be associated
1447 * @param mappingFunction the function to compute a value
1448 * @return the current (existing or computed) value associated with
1449 * the specified key, or null if the computed value is null
1450 * @throws NullPointerException if the specified key is null
1451 * or the mappingFunction is null
1452 * @since 1.8
1453 */
1454 public V computeIfAbsent(K key,
1455 Function<? super K, ? extends V> mappingFunction) {
1456 if (key == null || mappingFunction == null)
1457 throw new NullPointerException();
1458 V v, p, r;
1459 if ((v = doGet(key)) == null &&
1460 (r = mappingFunction.apply(key)) != null)
1461 v = (p = doPut(key, r, true)) == null ? r : p;
1462 return v;
1463 }
1464
1465 /**
1466 * If the value for the specified key is present, attempts to
1467 * compute a new mapping given the key and its current mapped
1468 * value. The function is <em>NOT</em> guaranteed to be applied
1469 * once atomically.
1470 *
1471 * @param key key with which a value may be associated
1472 * @param remappingFunction the function to compute a value
1473 * @return the new value associated with the specified key, or null if none
1474 * @throws NullPointerException if the specified key is null
1475 * or the remappingFunction is null
1476 * @since 1.8
1477 */
1478 public V computeIfPresent(K key,
1479 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1480 if (key == null || remappingFunction == null)
1481 throw new NullPointerException();
1482 Node<K,V> n; V v;
1483 while ((n = findNode(key)) != null) {
1484 if ((v = n.val) != null) {
1485 V r = remappingFunction.apply(key, v);
1486 if (r != null) {
1487 if (VAL.compareAndSet(n, v, r))
1488 return r;
1489 }
1490 else if (doRemove(key, v) != null)
1491 break;
1492 }
1493 }
1494 return null;
1495 }
1496
1497 /**
1498 * Attempts to compute a mapping for the specified key and its
1499 * current mapped value (or {@code null} if there is no current
1500 * mapping). The function is <em>NOT</em> guaranteed to be applied
1501 * once atomically.
1502 *
1503 * @param key key with which the specified value is to be associated
1504 * @param remappingFunction the function to compute a value
1505 * @return the new value associated with the specified key, or null if none
1506 * @throws NullPointerException if the specified key is null
1507 * or the remappingFunction is null
1508 * @since 1.8
1509 */
1510 public V compute(K key,
1511 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1512 if (key == null || remappingFunction == null)
1513 throw new NullPointerException();
1514 for (;;) {
1515 Node<K,V> n; V v; V r;
1516 if ((n = findNode(key)) == null) {
1517 if ((r = remappingFunction.apply(key, null)) == null)
1518 break;
1519 if (doPut(key, r, true) == null)
1520 return r;
1521 }
1522 else if ((v = n.val) != null) {
1523 if ((r = remappingFunction.apply(key, v)) != null) {
1524 if (VAL.compareAndSet(n, v, r))
1525 return r;
1526 }
1527 else if (doRemove(key, v) != null)
1528 break;
1529 }
1530 }
1531 return null;
1532 }
1533
1534 /**
1535 * If the specified key is not already associated with a value,
1536 * associates it with the given value. Otherwise, replaces the
1537 * value with the results of the given remapping function, or
1538 * removes if {@code null}. The function is <em>NOT</em>
1539 * guaranteed to be applied once atomically.
1540 *
1541 * @param key key with which the specified value is to be associated
1542 * @param value the value to use if absent
1543 * @param remappingFunction the function to recompute a value if present
1544 * @return the new value associated with the specified key, or null if none
1545 * @throws NullPointerException if the specified key or value is null
1546 * or the remappingFunction is null
1547 * @since 1.8
1548 */
1549 public V merge(K key, V value,
1550 BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1551 if (key == null || value == null || remappingFunction == null)
1552 throw new NullPointerException();
1553 for (;;) {
1554 Node<K,V> n; V v; V r;
1555 if ((n = findNode(key)) == null) {
1556 if (doPut(key, value, true) == null)
1557 return value;
1558 }
1559 else if ((v = n.val) != null) {
1560 if ((r = remappingFunction.apply(v, value)) != null) {
1561 if (VAL.compareAndSet(n, v, r))
1562 return r;
1563 }
1564 else if (doRemove(key, v) != null)
1565 return null;
1566 }
1567 }
1568 }
1569
1570 /* ---------------- View methods -------------- */
1571
1572 /*
1573 * Note: Lazy initialization works for views because view classes
1574 * are stateless/immutable so it doesn't matter wrt correctness if
1575 * more than one is created (which will only rarely happen). Even
1576 * so, the following idiom conservatively ensures that the method
1577 * returns the one it created if it does so, not one created by
1578 * another racing thread.
1579 */
1580
1581 /**
1582 * Returns a {@link NavigableSet} view of the keys contained in this map.
1583 *
1584 * <p>The set's iterator returns the keys in ascending order.
1585 * The set's spliterator additionally reports {@link Spliterator#CONCURRENT},
1586 * {@link Spliterator#NONNULL}, {@link Spliterator#SORTED} and
1587 * {@link Spliterator#ORDERED}, with an encounter order that is ascending
1588 * key order.
1589 *
1590 * <p>The {@linkplain Spliterator#getComparator() spliterator's comparator}
1591 * is {@code null} if the {@linkplain #comparator() map's comparator}
1592 * is {@code null}.
1593 * Otherwise, the spliterator's comparator is the same as or imposes the
1594 * same total ordering as the map's comparator.
1595 *
1596 * <p>The set is backed by the map, so changes to the map are
1597 * reflected in the set, and vice-versa. The set supports element
1598 * removal, which removes the corresponding mapping from the map,
1599 * via the {@code Iterator.remove}, {@code Set.remove},
1600 * {@code removeAll}, {@code retainAll}, and {@code clear}
1601 * operations. It does not support the {@code add} or {@code addAll}
1602 * operations.
1603 *
1604 * <p>The view's iterators and spliterators are
1605 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1606 *
1607 * <p>This method is equivalent to method {@code navigableKeySet}.
1608 *
1609 * @return a navigable set view of the keys in this map
1610 */
1611 public NavigableSet<K> keySet() {
1612 KeySet<K,V> ks;
1613 if ((ks = keySet) != null) return ks;
1614 return keySet = new KeySet<>(this);
1615 }
1616
1617 public NavigableSet<K> navigableKeySet() {
1618 KeySet<K,V> ks;
1619 if ((ks = keySet) != null) return ks;
1620 return keySet = new KeySet<>(this);
1621 }
1622
1623 /**
1624 * Returns a {@link Collection} view of the values contained in this map.
1625 * <p>The collection's iterator returns the values in ascending order
1626 * of the corresponding keys. The collections's spliterator additionally
1627 * reports {@link Spliterator#CONCURRENT}, {@link Spliterator#NONNULL} and
1628 * {@link Spliterator#ORDERED}, with an encounter order that is ascending
1629 * order of the corresponding keys.
1630 *
1631 * <p>The collection is backed by the map, so changes to the map are
1632 * reflected in the collection, and vice-versa. The collection
1633 * supports element removal, which removes the corresponding
1634 * mapping from the map, via the {@code Iterator.remove},
1635 * {@code Collection.remove}, {@code removeAll},
1636 * {@code retainAll} and {@code clear} operations. It does not
1637 * support the {@code add} or {@code addAll} operations.
1638 *
1639 * <p>The view's iterators and spliterators are
1640 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1641 */
1642 public Collection<V> values() {
1643 Values<K,V> vs;
1644 if ((vs = values) != null) return vs;
1645 return values = new Values<>(this);
1646 }
1647
1648 /**
1649 * Returns a {@link Set} view of the mappings contained in this map.
1650 *
1651 * <p>The set's iterator returns the entries in ascending key order. The
1652 * set's spliterator additionally reports {@link Spliterator#CONCURRENT},
1653 * {@link Spliterator#NONNULL}, {@link Spliterator#SORTED} and
1654 * {@link Spliterator#ORDERED}, with an encounter order that is ascending
1655 * key order.
1656 *
1657 * <p>The set is backed by the map, so changes to the map are
1658 * reflected in the set, and vice-versa. The set supports element
1659 * removal, which removes the corresponding mapping from the map,
1660 * via the {@code Iterator.remove}, {@code Set.remove},
1661 * {@code removeAll}, {@code retainAll} and {@code clear}
1662 * operations. It does not support the {@code add} or
1663 * {@code addAll} operations.
1664 *
1665 * <p>The view's iterators and spliterators are
1666 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1667 *
1668 * <p>The {@code Map.Entry} elements traversed by the {@code iterator}
1669 * or {@code spliterator} do <em>not</em> support the {@code setValue}
1670 * operation.
1671 *
1672 * @return a set view of the mappings contained in this map,
1673 * sorted in ascending key order
1674 */
1675 public Set<Map.Entry<K,V>> entrySet() {
1676 EntrySet<K,V> es;
1677 if ((es = entrySet) != null) return es;
1678 return entrySet = new EntrySet<K,V>(this);
1679 }
1680
1681 public ConcurrentNavigableMap<K,V> descendingMap() {
1682 ConcurrentNavigableMap<K,V> dm;
1683 if ((dm = descendingMap) != null) return dm;
1684 return descendingMap =
1685 new SubMap<K,V>(this, null, false, null, false, true);
1686 }
1687
1688 public NavigableSet<K> descendingKeySet() {
1689 return descendingMap().navigableKeySet();
1690 }
1691
1692 /* ---------------- AbstractMap Overrides -------------- */
1693
1694 /**
1695 * Compares the specified object with this map for equality.
1696 * Returns {@code true} if the given object is also a map and the
1697 * two maps represent the same mappings. More formally, two maps
1698 * {@code m1} and {@code m2} represent the same mappings if
1699 * {@code m1.entrySet().equals(m2.entrySet())}. This
1700 * operation may return misleading results if either map is
1701 * concurrently modified during execution of this method.
1702 *
1703 * @param o object to be compared for equality with this map
1704 * @return {@code true} if the specified object is equal to this map
1705 */
1706 public boolean equals(Object o) {
1707 if (o == this)
1708 return true;
1709 if (!(o instanceof Map))
1710 return false;
1711 Map<?,?> m = (Map<?,?>) o;
1712 try {
1713 Comparator<? super K> cmp = comparator;
1714 @SuppressWarnings("unchecked")
1715 Iterator<Map.Entry<?,?>> it =
1716 (Iterator<Map.Entry<?,?>>)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 unused) {
1768 return false;
1769 } catch (NullPointerException unused) {
1770 return false;
1771 }
1772 }
1773
1774 /* ------ ConcurrentMap API methods ------ */
1775
1776 /**
1777 * {@inheritDoc}
1778 *
1779 * @return the previous value associated with the specified key,
1780 * or {@code null} if there was no mapping for the key
1781 * @throws ClassCastException if the specified key cannot be compared
1782 * with the keys currently in the map
1783 * @throws NullPointerException if the specified key or value is null
1784 */
1785 public V putIfAbsent(K key, V value) {
1786 if (value == null)
1787 throw new NullPointerException();
1788 return doPut(key, value, true);
1789 }
1790
1791 /**
1792 * {@inheritDoc}
1793 *
1794 * @throws ClassCastException if the specified key cannot be compared
1795 * with the keys currently in the map
1796 * @throws NullPointerException if the specified key is null
1797 */
1798 public boolean remove(Object key, Object value) {
1799 if (key == null)
1800 throw new NullPointerException();
1801 return value != null && doRemove(key, value) != null;
1802 }
1803
1804 /**
1805 * {@inheritDoc}
1806 *
1807 * @throws ClassCastException if the specified key cannot be compared
1808 * with the keys currently in the map
1809 * @throws NullPointerException if any of the arguments are null
1810 */
1811 public boolean replace(K key, V oldValue, V newValue) {
1812 if (key == null || oldValue == null || newValue == null)
1813 throw new NullPointerException();
1814 for (;;) {
1815 Node<K,V> n; V v;
1816 if ((n = findNode(key)) == null)
1817 return false;
1818 if ((v = n.val) != null) {
1819 if (!oldValue.equals(v))
1820 return false;
1821 if (VAL.compareAndSet(n, v, newValue))
1822 return true;
1823 }
1824 }
1825 }
1826
1827 /**
1828 * {@inheritDoc}
1829 *
1830 * @return the previous value associated with the specified key,
1831 * or {@code null} if there was no mapping for the key
1832 * @throws ClassCastException if the specified key cannot be compared
1833 * with the keys currently in the map
1834 * @throws NullPointerException if the specified key or value is null
1835 */
1836 public V replace(K key, V value) {
1837 if (key == null || value == null)
1838 throw new NullPointerException();
1839 for (;;) {
1840 Node<K,V> n; V v;
1841 if ((n = findNode(key)) == null)
1842 return null;
1843 if ((v = n.val) != null && VAL.compareAndSet(n, v, value))
1844 return v;
1845 }
1846 }
1847
1848 /* ------ SortedMap API methods ------ */
1849
1850 public Comparator<? super K> comparator() {
1851 return comparator;
1852 }
1853
1854 /**
1855 * @throws NoSuchElementException {@inheritDoc}
1856 */
1857 public K firstKey() {
1858 Node<K,V> n = findFirst();
1859 if (n == null)
1860 throw new NoSuchElementException();
1861 return n.key;
1862 }
1863
1864 /**
1865 * @throws NoSuchElementException {@inheritDoc}
1866 */
1867 public K lastKey() {
1868 Node<K,V> n = findLast();
1869 if (n == null)
1870 throw new NoSuchElementException();
1871 return n.key;
1872 }
1873
1874 /**
1875 * @throws ClassCastException {@inheritDoc}
1876 * @throws NullPointerException if {@code fromKey} or {@code toKey} is null
1877 * @throws IllegalArgumentException {@inheritDoc}
1878 */
1879 public ConcurrentNavigableMap<K,V> subMap(K fromKey,
1880 boolean fromInclusive,
1881 K toKey,
1882 boolean toInclusive) {
1883 if (fromKey == null || toKey == null)
1884 throw new NullPointerException();
1885 return new SubMap<K,V>
1886 (this, fromKey, fromInclusive, toKey, toInclusive, false);
1887 }
1888
1889 /**
1890 * @throws ClassCastException {@inheritDoc}
1891 * @throws NullPointerException if {@code toKey} is null
1892 * @throws IllegalArgumentException {@inheritDoc}
1893 */
1894 public ConcurrentNavigableMap<K,V> headMap(K toKey,
1895 boolean inclusive) {
1896 if (toKey == null)
1897 throw new NullPointerException();
1898 return new SubMap<K,V>
1899 (this, null, false, toKey, inclusive, false);
1900 }
1901
1902 /**
1903 * @throws ClassCastException {@inheritDoc}
1904 * @throws NullPointerException if {@code fromKey} is null
1905 * @throws IllegalArgumentException {@inheritDoc}
1906 */
1907 public ConcurrentNavigableMap<K,V> tailMap(K fromKey,
1908 boolean inclusive) {
1909 if (fromKey == null)
1910 throw new NullPointerException();
1911 return new SubMap<K,V>
1912 (this, fromKey, inclusive, null, false, false);
1913 }
1914
1915 /**
1916 * @throws ClassCastException {@inheritDoc}
1917 * @throws NullPointerException if {@code fromKey} or {@code toKey} is null
1918 * @throws IllegalArgumentException {@inheritDoc}
1919 */
1920 public ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey) {
1921 return subMap(fromKey, true, toKey, false);
1922 }
1923
1924 /**
1925 * @throws ClassCastException {@inheritDoc}
1926 * @throws NullPointerException if {@code toKey} is null
1927 * @throws IllegalArgumentException {@inheritDoc}
1928 */
1929 public ConcurrentNavigableMap<K,V> headMap(K toKey) {
1930 return headMap(toKey, false);
1931 }
1932
1933 /**
1934 * @throws ClassCastException {@inheritDoc}
1935 * @throws NullPointerException if {@code fromKey} is null
1936 * @throws IllegalArgumentException {@inheritDoc}
1937 */
1938 public ConcurrentNavigableMap<K,V> tailMap(K fromKey) {
1939 return tailMap(fromKey, true);
1940 }
1941
1942 /* ---------------- Relational operations -------------- */
1943
1944 /**
1945 * Returns a key-value mapping associated with the greatest key
1946 * strictly less than the given key, or {@code null} if there is
1947 * no such key. The returned entry does <em>not</em> support the
1948 * {@code Entry.setValue} method.
1949 *
1950 * @throws ClassCastException {@inheritDoc}
1951 * @throws NullPointerException if the specified key is null
1952 */
1953 public Map.Entry<K,V> lowerEntry(K key) {
1954 return findNearEntry(key, LT, comparator);
1955 }
1956
1957 /**
1958 * @throws ClassCastException {@inheritDoc}
1959 * @throws NullPointerException if the specified key is null
1960 */
1961 public K lowerKey(K key) {
1962 Node<K,V> n = findNear(key, LT, comparator);
1963 return (n == null) ? null : n.key;
1964 }
1965
1966 /**
1967 * Returns a key-value mapping associated with the greatest key
1968 * less than or equal to the given key, or {@code null} if there
1969 * is no such key. The returned entry does <em>not</em> support
1970 * the {@code Entry.setValue} method.
1971 *
1972 * @param key the key
1973 * @throws ClassCastException {@inheritDoc}
1974 * @throws NullPointerException if the specified key is null
1975 */
1976 public Map.Entry<K,V> floorEntry(K key) {
1977 return findNearEntry(key, LT|EQ, comparator);
1978 }
1979
1980 /**
1981 * @param key the key
1982 * @throws ClassCastException {@inheritDoc}
1983 * @throws NullPointerException if the specified key is null
1984 */
1985 public K floorKey(K key) {
1986 Node<K,V> n = findNear(key, LT|EQ, comparator);
1987 return (n == null) ? null : n.key;
1988 }
1989
1990 /**
1991 * Returns a key-value mapping associated with the least key
1992 * greater than or equal to the given key, or {@code null} if
1993 * there is no such entry. The returned entry does <em>not</em>
1994 * support the {@code Entry.setValue} method.
1995 *
1996 * @throws ClassCastException {@inheritDoc}
1997 * @throws NullPointerException if the specified key is null
1998 */
1999 public Map.Entry<K,V> ceilingEntry(K key) {
2000 return findNearEntry(key, GT|EQ, comparator);
2001 }
2002
2003 /**
2004 * @throws ClassCastException {@inheritDoc}
2005 * @throws NullPointerException if the specified key is null
2006 */
2007 public K ceilingKey(K key) {
2008 Node<K,V> n = findNear(key, GT|EQ, comparator);
2009 return (n == null) ? null : n.key;
2010 }
2011
2012 /**
2013 * Returns a key-value mapping associated with the least key
2014 * strictly greater than the given key, or {@code null} if there
2015 * is no such key. The returned entry does <em>not</em> support
2016 * the {@code Entry.setValue} method.
2017 *
2018 * @param key the key
2019 * @throws ClassCastException {@inheritDoc}
2020 * @throws NullPointerException if the specified key is null
2021 */
2022 public Map.Entry<K,V> higherEntry(K key) {
2023 return findNearEntry(key, GT, comparator);
2024 }
2025
2026 /**
2027 * @param key the key
2028 * @throws ClassCastException {@inheritDoc}
2029 * @throws NullPointerException if the specified key is null
2030 */
2031 public K higherKey(K key) {
2032 Node<K,V> n = findNear(key, GT, comparator);
2033 return (n == null) ? null : n.key;
2034 }
2035
2036 /**
2037 * Returns a key-value mapping associated with the least
2038 * key in this map, or {@code null} if the map is empty.
2039 * The returned entry does <em>not</em> support
2040 * the {@code Entry.setValue} method.
2041 */
2042 public Map.Entry<K,V> firstEntry() {
2043 return findFirstEntry();
2044 }
2045
2046 /**
2047 * Returns a key-value mapping associated with the greatest
2048 * key in this map, or {@code null} if the map is empty.
2049 * The returned entry does <em>not</em> support
2050 * the {@code Entry.setValue} method.
2051 */
2052 public Map.Entry<K,V> lastEntry() {
2053 return findLastEntry();
2054 }
2055
2056 /**
2057 * Removes and returns a key-value mapping associated with
2058 * the least key in this map, or {@code null} if the map is empty.
2059 * The returned entry does <em>not</em> support
2060 * the {@code Entry.setValue} method.
2061 */
2062 public Map.Entry<K,V> pollFirstEntry() {
2063 return doRemoveFirstEntry();
2064 }
2065
2066 /**
2067 * Removes and returns a key-value mapping associated with
2068 * the greatest key in this map, or {@code null} if the map is empty.
2069 * The returned entry does <em>not</em> support
2070 * the {@code Entry.setValue} method.
2071 */
2072 public Map.Entry<K,V> pollLastEntry() {
2073 return doRemoveLastEntry();
2074 }
2075
2076 /* ---------------- Iterators -------------- */
2077
2078 /**
2079 * Base of iterator classes
2080 */
2081 abstract class Iter<T> implements Iterator<T> {
2082 /** the last node returned by next() */
2083 Node<K,V> lastReturned;
2084 /** the next node to return from next(); */
2085 Node<K,V> next;
2086 /** Cache of next value field to maintain weak consistency */
2087 V nextValue;
2088
2089 /** Initializes ascending iterator for entire range. */
2090 Iter() {
2091 advance(baseHead());
2092 }
2093
2094 public final boolean hasNext() {
2095 return next != null;
2096 }
2097
2098 /** Advances next to higher entry. */
2099 final void advance(Node<K,V> b) {
2100 Node<K,V> n = null;
2101 V v = null;
2102 if ((lastReturned = b) != null) {
2103 while ((n = b.next) != null && (v = n.val) == null)
2104 b = n;
2105 }
2106 nextValue = v;
2107 next = n;
2108 }
2109
2110 public final void remove() {
2111 Node<K,V> n; K k;
2112 if ((n = lastReturned) == null || (k = n.key) == null)
2113 throw new IllegalStateException();
2114 // It would not be worth all of the overhead to directly
2115 // unlink from here. Using remove is fast enough.
2116 ConcurrentSkipListMap.this.remove(k);
2117 lastReturned = null;
2118 }
2119 }
2120
2121 final class ValueIterator extends Iter<V> {
2122 public V next() {
2123 V v;
2124 if ((v = nextValue) == null)
2125 throw new NoSuchElementException();
2126 advance(next);
2127 return v;
2128 }
2129 }
2130
2131 final class KeyIterator extends Iter<K> {
2132 public K next() {
2133 Node<K,V> n;
2134 if ((n = next) == null)
2135 throw new NoSuchElementException();
2136 K k = n.key;
2137 advance(n);
2138 return k;
2139 }
2140 }
2141
2142 final class EntryIterator extends Iter<Map.Entry<K,V>> {
2143 public Map.Entry<K,V> next() {
2144 Node<K,V> n;
2145 if ((n = next) == null)
2146 throw new NoSuchElementException();
2147 K k = n.key;
2148 V v = nextValue;
2149 advance(n);
2150 return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2151 }
2152 }
2153
2154 /* ---------------- View Classes -------------- */
2155
2156 /*
2157 * View classes are static, delegating to a ConcurrentNavigableMap
2158 * to allow use by SubMaps, which outweighs the ugliness of
2159 * needing type-tests for Iterator methods.
2160 */
2161
2162 static final <E> List<E> toList(Collection<E> c) {
2163 // Using size() here would be a pessimization.
2164 ArrayList<E> list = new ArrayList<E>();
2165 for (E e : c)
2166 list.add(e);
2167 return list;
2168 }
2169
2170 static final class KeySet<K,V>
2171 extends AbstractSet<K> implements NavigableSet<K> {
2172 final ConcurrentNavigableMap<K,V> m;
2173 KeySet(ConcurrentNavigableMap<K,V> map) { m = map; }
2174 public int size() { return m.size(); }
2175 public boolean isEmpty() { return m.isEmpty(); }
2176 public boolean contains(Object o) { return m.containsKey(o); }
2177 public boolean remove(Object o) { return m.remove(o) != null; }
2178 public void clear() { m.clear(); }
2179 public K lower(K e) { return m.lowerKey(e); }
2180 public K floor(K e) { return m.floorKey(e); }
2181 public K ceiling(K e) { return m.ceilingKey(e); }
2182 public K higher(K e) { return m.higherKey(e); }
2183 public Comparator<? super K> comparator() { return m.comparator(); }
2184 public K first() { return m.firstKey(); }
2185 public K last() { return m.lastKey(); }
2186 public K pollFirst() {
2187 Map.Entry<K,V> e = m.pollFirstEntry();
2188 return (e == null) ? null : e.getKey();
2189 }
2190 public K pollLast() {
2191 Map.Entry<K,V> e = m.pollLastEntry();
2192 return (e == null) ? null : e.getKey();
2193 }
2194 public Iterator<K> iterator() {
2195 return (m instanceof ConcurrentSkipListMap)
2196 ? ((ConcurrentSkipListMap<K,V>)m).new KeyIterator()
2197 : ((SubMap<K,V>)m).new SubMapKeyIterator();
2198 }
2199 public boolean equals(Object o) {
2200 if (o == this)
2201 return true;
2202 if (!(o instanceof Set))
2203 return false;
2204 Collection<?> c = (Collection<?>) o;
2205 try {
2206 return containsAll(c) && c.containsAll(this);
2207 } catch (ClassCastException | NullPointerException unused) {
2208 return false;
2209 }
2210 }
2211 public Object[] toArray() { return toList(this).toArray(); }
2212 public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
2213 public Iterator<K> descendingIterator() {
2214 return descendingSet().iterator();
2215 }
2216 public NavigableSet<K> subSet(K fromElement,
2217 boolean fromInclusive,
2218 K toElement,
2219 boolean toInclusive) {
2220 return new KeySet<>(m.subMap(fromElement, fromInclusive,
2221 toElement, toInclusive));
2222 }
2223 public NavigableSet<K> headSet(K toElement, boolean inclusive) {
2224 return new KeySet<>(m.headMap(toElement, inclusive));
2225 }
2226 public NavigableSet<K> tailSet(K fromElement, boolean inclusive) {
2227 return new KeySet<>(m.tailMap(fromElement, inclusive));
2228 }
2229 public NavigableSet<K> subSet(K fromElement, K toElement) {
2230 return subSet(fromElement, true, toElement, false);
2231 }
2232 public NavigableSet<K> headSet(K toElement) {
2233 return headSet(toElement, false);
2234 }
2235 public NavigableSet<K> tailSet(K fromElement) {
2236 return tailSet(fromElement, true);
2237 }
2238 public NavigableSet<K> descendingSet() {
2239 return new KeySet<>(m.descendingMap());
2240 }
2241
2242 public Spliterator<K> spliterator() {
2243 return (m instanceof ConcurrentSkipListMap)
2244 ? ((ConcurrentSkipListMap<K,V>)m).keySpliterator()
2245 : ((SubMap<K,V>)m).new SubMapKeyIterator();
2246 }
2247 }
2248
2249 static final class Values<K,V> extends AbstractCollection<V> {
2250 final ConcurrentNavigableMap<K,V> m;
2251 Values(ConcurrentNavigableMap<K,V> map) {
2252 m = map;
2253 }
2254 public Iterator<V> iterator() {
2255 return (m instanceof ConcurrentSkipListMap)
2256 ? ((ConcurrentSkipListMap<K,V>)m).new ValueIterator()
2257 : ((SubMap<K,V>)m).new SubMapValueIterator();
2258 }
2259 public int size() { return m.size(); }
2260 public boolean isEmpty() { return m.isEmpty(); }
2261 public boolean contains(Object o) { return m.containsValue(o); }
2262 public void clear() { m.clear(); }
2263 public Object[] toArray() { return toList(this).toArray(); }
2264 public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
2265
2266 public Spliterator<V> spliterator() {
2267 return (m instanceof ConcurrentSkipListMap)
2268 ? ((ConcurrentSkipListMap<K,V>)m).valueSpliterator()
2269 : ((SubMap<K,V>)m).new SubMapValueIterator();
2270 }
2271
2272 public boolean removeIf(Predicate<? super V> filter) {
2273 if (filter == null) throw new NullPointerException();
2274 if (m instanceof ConcurrentSkipListMap)
2275 return ((ConcurrentSkipListMap<K,V>)m).removeValueIf(filter);
2276 // else use iterator
2277 Iterator<Map.Entry<K,V>> it =
2278 ((SubMap<K,V>)m).new SubMapEntryIterator();
2279 boolean removed = false;
2280 while (it.hasNext()) {
2281 Map.Entry<K,V> e = it.next();
2282 V v = e.getValue();
2283 if (filter.test(v) && m.remove(e.getKey(), v))
2284 removed = true;
2285 }
2286 return removed;
2287 }
2288 }
2289
2290 static final class EntrySet<K,V> extends AbstractSet<Map.Entry<K,V>> {
2291 final ConcurrentNavigableMap<K,V> m;
2292 EntrySet(ConcurrentNavigableMap<K,V> map) {
2293 m = map;
2294 }
2295 public Iterator<Map.Entry<K,V>> iterator() {
2296 return (m instanceof ConcurrentSkipListMap)
2297 ? ((ConcurrentSkipListMap<K,V>)m).new EntryIterator()
2298 : ((SubMap<K,V>)m).new SubMapEntryIterator();
2299 }
2300
2301 public boolean contains(Object o) {
2302 if (!(o instanceof Map.Entry))
2303 return false;
2304 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
2305 V v = m.get(e.getKey());
2306 return v != null && v.equals(e.getValue());
2307 }
2308 public boolean remove(Object o) {
2309 if (!(o instanceof Map.Entry))
2310 return false;
2311 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
2312 return m.remove(e.getKey(),
2313 e.getValue());
2314 }
2315 public boolean isEmpty() {
2316 return m.isEmpty();
2317 }
2318 public int size() {
2319 return m.size();
2320 }
2321 public void clear() {
2322 m.clear();
2323 }
2324 public boolean equals(Object o) {
2325 if (o == this)
2326 return true;
2327 if (!(o instanceof Set))
2328 return false;
2329 Collection<?> c = (Collection<?>) o;
2330 try {
2331 return containsAll(c) && c.containsAll(this);
2332 } catch (ClassCastException | NullPointerException unused) {
2333 return false;
2334 }
2335 }
2336 public Object[] toArray() { return toList(this).toArray(); }
2337 public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
2338
2339 public Spliterator<Map.Entry<K,V>> spliterator() {
2340 return (m instanceof ConcurrentSkipListMap)
2341 ? ((ConcurrentSkipListMap<K,V>)m).entrySpliterator()
2342 : ((SubMap<K,V>)m).new SubMapEntryIterator();
2343 }
2344 public boolean removeIf(Predicate<? super Entry<K,V>> filter) {
2345 if (filter == null) throw new NullPointerException();
2346 if (m instanceof ConcurrentSkipListMap)
2347 return ((ConcurrentSkipListMap<K,V>)m).removeEntryIf(filter);
2348 // else use iterator
2349 Iterator<Map.Entry<K,V>> it =
2350 ((SubMap<K,V>)m).new SubMapEntryIterator();
2351 boolean removed = false;
2352 while (it.hasNext()) {
2353 Map.Entry<K,V> e = it.next();
2354 if (filter.test(e) && m.remove(e.getKey(), e.getValue()))
2355 removed = true;
2356 }
2357 return removed;
2358 }
2359 }
2360
2361 /**
2362 * Submaps returned by {@link ConcurrentSkipListMap} submap operations
2363 * represent a subrange of mappings of their underlying maps.
2364 * Instances of this class support all methods of their underlying
2365 * maps, differing in that mappings outside their range are ignored,
2366 * and attempts to add mappings outside their ranges result in {@link
2367 * IllegalArgumentException}. Instances of this class are constructed
2368 * only using the {@code subMap}, {@code headMap}, and {@code tailMap}
2369 * methods of their underlying maps.
2370 *
2371 * @serial include
2372 */
2373 static final class SubMap<K,V> extends AbstractMap<K,V>
2374 implements ConcurrentNavigableMap<K,V>, Serializable {
2375 private static final long serialVersionUID = -7647078645895051609L;
2376
2377 /** Underlying map */
2378 final ConcurrentSkipListMap<K,V> m;
2379 /** lower bound key, or null if from start */
2380 private final K lo;
2381 /** upper bound key, or null if to end */
2382 private final K hi;
2383 /** inclusion flag for lo */
2384 private final boolean loInclusive;
2385 /** inclusion flag for hi */
2386 private final boolean hiInclusive;
2387 /** direction */
2388 final boolean isDescending;
2389
2390 // Lazily initialized view holders
2391 private transient KeySet<K,V> keySetView;
2392 private transient Values<K,V> valuesView;
2393 private transient EntrySet<K,V> entrySetView;
2394
2395 /**
2396 * Creates a new submap, initializing all fields.
2397 */
2398 SubMap(ConcurrentSkipListMap<K,V> map,
2399 K fromKey, boolean fromInclusive,
2400 K toKey, boolean toInclusive,
2401 boolean isDescending) {
2402 Comparator<? super K> cmp = map.comparator;
2403 if (fromKey != null && toKey != null &&
2404 cpr(cmp, fromKey, toKey) > 0)
2405 throw new IllegalArgumentException("inconsistent range");
2406 this.m = map;
2407 this.lo = fromKey;
2408 this.hi = toKey;
2409 this.loInclusive = fromInclusive;
2410 this.hiInclusive = toInclusive;
2411 this.isDescending = isDescending;
2412 }
2413
2414 /* ---------------- Utilities -------------- */
2415
2416 boolean tooLow(Object key, Comparator<? super K> cmp) {
2417 int c;
2418 return (lo != null && ((c = cpr(cmp, key, lo)) < 0 ||
2419 (c == 0 && !loInclusive)));
2420 }
2421
2422 boolean tooHigh(Object key, Comparator<? super K> cmp) {
2423 int c;
2424 return (hi != null && ((c = cpr(cmp, key, hi)) > 0 ||
2425 (c == 0 && !hiInclusive)));
2426 }
2427
2428 boolean inBounds(Object key, Comparator<? super K> cmp) {
2429 return !tooLow(key, cmp) && !tooHigh(key, cmp);
2430 }
2431
2432 void checkKeyBounds(K key, Comparator<? super K> cmp) {
2433 if (key == null)
2434 throw new NullPointerException();
2435 if (!inBounds(key, cmp))
2436 throw new IllegalArgumentException("key out of range");
2437 }
2438
2439 /**
2440 * Returns true if node key is less than upper bound of range.
2441 */
2442 boolean isBeforeEnd(ConcurrentSkipListMap.Node<K,V> n,
2443 Comparator<? super K> cmp) {
2444 if (n == null)
2445 return false;
2446 if (hi == null)
2447 return true;
2448 K k = n.key;
2449 if (k == null) // pass by markers and headers
2450 return true;
2451 int c = cpr(cmp, k, hi);
2452 return c < 0 || (c == 0 && hiInclusive);
2453 }
2454
2455 /**
2456 * Returns lowest node. This node might not be in range, so
2457 * most usages need to check bounds.
2458 */
2459 ConcurrentSkipListMap.Node<K,V> loNode(Comparator<? super K> cmp) {
2460 if (lo == null)
2461 return m.findFirst();
2462 else if (loInclusive)
2463 return m.findNear(lo, GT|EQ, cmp);
2464 else
2465 return m.findNear(lo, GT, cmp);
2466 }
2467
2468 /**
2469 * Returns highest node. This node might not be in range, so
2470 * most usages need to check bounds.
2471 */
2472 ConcurrentSkipListMap.Node<K,V> hiNode(Comparator<? super K> cmp) {
2473 if (hi == null)
2474 return m.findLast();
2475 else if (hiInclusive)
2476 return m.findNear(hi, LT|EQ, cmp);
2477 else
2478 return m.findNear(hi, LT, cmp);
2479 }
2480
2481 /**
2482 * Returns lowest absolute key (ignoring directionality).
2483 */
2484 K lowestKey() {
2485 Comparator<? super K> cmp = m.comparator;
2486 ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
2487 if (isBeforeEnd(n, cmp))
2488 return n.key;
2489 else
2490 throw new NoSuchElementException();
2491 }
2492
2493 /**
2494 * Returns highest absolute key (ignoring directionality).
2495 */
2496 K highestKey() {
2497 Comparator<? super K> cmp = m.comparator;
2498 ConcurrentSkipListMap.Node<K,V> n = hiNode(cmp);
2499 if (n != null) {
2500 K last = n.key;
2501 if (inBounds(last, cmp))
2502 return last;
2503 }
2504 throw new NoSuchElementException();
2505 }
2506
2507 Map.Entry<K,V> lowestEntry() {
2508 Comparator<? super K> cmp = m.comparator;
2509 for (;;) {
2510 ConcurrentSkipListMap.Node<K,V> n; V v;
2511 if ((n = loNode(cmp)) == null || !isBeforeEnd(n, cmp))
2512 return null;
2513 else if ((v = n.val) != null)
2514 return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
2515 }
2516 }
2517
2518 Map.Entry<K,V> highestEntry() {
2519 Comparator<? super K> cmp = m.comparator;
2520 for (;;) {
2521 ConcurrentSkipListMap.Node<K,V> n; V v;
2522 if ((n = hiNode(cmp)) == null || !inBounds(n.key, cmp))
2523 return null;
2524 else if ((v = n.val) != null)
2525 return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
2526 }
2527 }
2528
2529 Map.Entry<K,V> removeLowest() {
2530 Comparator<? super K> cmp = m.comparator;
2531 for (;;) {
2532 ConcurrentSkipListMap.Node<K,V> n; K k; V v;
2533 if ((n = loNode(cmp)) == null)
2534 return null;
2535 else if (!inBounds((k = n.key), cmp))
2536 return null;
2537 else if ((v = m.doRemove(k, null)) != null)
2538 return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2539 }
2540 }
2541
2542 Map.Entry<K,V> removeHighest() {
2543 Comparator<? super K> cmp = m.comparator;
2544 for (;;) {
2545 ConcurrentSkipListMap.Node<K,V> n; K k; V v;
2546 if ((n = hiNode(cmp)) == null)
2547 return null;
2548 else if (!inBounds((k = n.key), cmp))
2549 return null;
2550 else if ((v = m.doRemove(k, null)) != null)
2551 return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2552 }
2553 }
2554
2555 /**
2556 * Submap version of ConcurrentSkipListMap.findNearEntry.
2557 */
2558 Map.Entry<K,V> getNearEntry(K key, int rel) {
2559 Comparator<? super K> cmp = m.comparator;
2560 if (isDescending) { // adjust relation for direction
2561 if ((rel & LT) == 0)
2562 rel |= LT;
2563 else
2564 rel &= ~LT;
2565 }
2566 if (tooLow(key, cmp))
2567 return ((rel & LT) != 0) ? null : lowestEntry();
2568 if (tooHigh(key, cmp))
2569 return ((rel & LT) != 0) ? highestEntry() : null;
2570 AbstractMap.SimpleImmutableEntry<K,V> e =
2571 m.findNearEntry(key, rel, cmp);
2572 if (e == null || !inBounds(e.getKey(), cmp))
2573 return null;
2574 else
2575 return e;
2576 }
2577
2578 // Almost the same as getNearEntry, except for keys
2579 K getNearKey(K key, int rel) {
2580 Comparator<? super K> cmp = m.comparator;
2581 if (isDescending) { // adjust relation for direction
2582 if ((rel & LT) == 0)
2583 rel |= LT;
2584 else
2585 rel &= ~LT;
2586 }
2587 if (tooLow(key, cmp)) {
2588 if ((rel & LT) == 0) {
2589 ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
2590 if (isBeforeEnd(n, cmp))
2591 return n.key;
2592 }
2593 return null;
2594 }
2595 if (tooHigh(key, cmp)) {
2596 if ((rel & LT) != 0) {
2597 ConcurrentSkipListMap.Node<K,V> n = hiNode(cmp);
2598 if (n != null) {
2599 K last = n.key;
2600 if (inBounds(last, cmp))
2601 return last;
2602 }
2603 }
2604 return null;
2605 }
2606 for (;;) {
2607 Node<K,V> n = m.findNear(key, rel, cmp);
2608 if (n == null || !inBounds(n.key, cmp))
2609 return null;
2610 if (n.val != null)
2611 return n.key;
2612 }
2613 }
2614
2615 /* ---------------- Map API methods -------------- */
2616
2617 public boolean containsKey(Object key) {
2618 if (key == null) throw new NullPointerException();
2619 return inBounds(key, m.comparator) && m.containsKey(key);
2620 }
2621
2622 public V get(Object key) {
2623 if (key == null) throw new NullPointerException();
2624 return (!inBounds(key, m.comparator)) ? null : m.get(key);
2625 }
2626
2627 public V put(K key, V value) {
2628 checkKeyBounds(key, m.comparator);
2629 return m.put(key, value);
2630 }
2631
2632 public V remove(Object key) {
2633 return (!inBounds(key, m.comparator)) ? null : m.remove(key);
2634 }
2635
2636 public int size() {
2637 Comparator<? super K> cmp = m.comparator;
2638 long count = 0;
2639 for (ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
2640 isBeforeEnd(n, cmp);
2641 n = n.next) {
2642 if (n.val != null)
2643 ++count;
2644 }
2645 return count >= Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)count;
2646 }
2647
2648 public boolean isEmpty() {
2649 Comparator<? super K> cmp = m.comparator;
2650 return !isBeforeEnd(loNode(cmp), cmp);
2651 }
2652
2653 public boolean containsValue(Object value) {
2654 if (value == null)
2655 throw new NullPointerException();
2656 Comparator<? super K> cmp = m.comparator;
2657 for (ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
2658 isBeforeEnd(n, cmp);
2659 n = n.next) {
2660 V v = n.val;
2661 if (v != null && value.equals(v))
2662 return true;
2663 }
2664 return false;
2665 }
2666
2667 public void clear() {
2668 Comparator<? super K> cmp = m.comparator;
2669 for (ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
2670 isBeforeEnd(n, cmp);
2671 n = n.next) {
2672 if (n.val != null)
2673 m.remove(n.key);
2674 }
2675 }
2676
2677 /* ---------------- ConcurrentMap API methods -------------- */
2678
2679 public V putIfAbsent(K key, V value) {
2680 checkKeyBounds(key, m.comparator);
2681 return m.putIfAbsent(key, value);
2682 }
2683
2684 public boolean remove(Object key, Object value) {
2685 return inBounds(key, m.comparator) && m.remove(key, value);
2686 }
2687
2688 public boolean replace(K key, V oldValue, V newValue) {
2689 checkKeyBounds(key, m.comparator);
2690 return m.replace(key, oldValue, newValue);
2691 }
2692
2693 public V replace(K key, V value) {
2694 checkKeyBounds(key, m.comparator);
2695 return m.replace(key, value);
2696 }
2697
2698 /* ---------------- SortedMap API methods -------------- */
2699
2700 public Comparator<? super K> comparator() {
2701 Comparator<? super K> cmp = m.comparator();
2702 if (isDescending)
2703 return Collections.reverseOrder(cmp);
2704 else
2705 return cmp;
2706 }
2707
2708 /**
2709 * Utility to create submaps, where given bounds override
2710 * unbounded(null) ones and/or are checked against bounded ones.
2711 */
2712 SubMap<K,V> newSubMap(K fromKey, boolean fromInclusive,
2713 K toKey, boolean toInclusive) {
2714 Comparator<? super K> cmp = m.comparator;
2715 if (isDescending) { // flip senses
2716 K tk = fromKey;
2717 fromKey = toKey;
2718 toKey = tk;
2719 boolean ti = fromInclusive;
2720 fromInclusive = toInclusive;
2721 toInclusive = ti;
2722 }
2723 if (lo != null) {
2724 if (fromKey == null) {
2725 fromKey = lo;
2726 fromInclusive = loInclusive;
2727 }
2728 else {
2729 int c = cpr(cmp, fromKey, lo);
2730 if (c < 0 || (c == 0 && !loInclusive && fromInclusive))
2731 throw new IllegalArgumentException("key out of range");
2732 }
2733 }
2734 if (hi != null) {
2735 if (toKey == null) {
2736 toKey = hi;
2737 toInclusive = hiInclusive;
2738 }
2739 else {
2740 int c = cpr(cmp, toKey, hi);
2741 if (c > 0 || (c == 0 && !hiInclusive && toInclusive))
2742 throw new IllegalArgumentException("key out of range");
2743 }
2744 }
2745 return new SubMap<K,V>(m, fromKey, fromInclusive,
2746 toKey, toInclusive, isDescending);
2747 }
2748
2749 public SubMap<K,V> subMap(K fromKey, boolean fromInclusive,
2750 K toKey, boolean toInclusive) {
2751 if (fromKey == null || toKey == null)
2752 throw new NullPointerException();
2753 return newSubMap(fromKey, fromInclusive, toKey, toInclusive);
2754 }
2755
2756 public SubMap<K,V> headMap(K toKey, boolean inclusive) {
2757 if (toKey == null)
2758 throw new NullPointerException();
2759 return newSubMap(null, false, toKey, inclusive);
2760 }
2761
2762 public SubMap<K,V> tailMap(K fromKey, boolean inclusive) {
2763 if (fromKey == null)
2764 throw new NullPointerException();
2765 return newSubMap(fromKey, inclusive, null, false);
2766 }
2767
2768 public SubMap<K,V> subMap(K fromKey, K toKey) {
2769 return subMap(fromKey, true, toKey, false);
2770 }
2771
2772 public SubMap<K,V> headMap(K toKey) {
2773 return headMap(toKey, false);
2774 }
2775
2776 public SubMap<K,V> tailMap(K fromKey) {
2777 return tailMap(fromKey, true);
2778 }
2779
2780 public SubMap<K,V> descendingMap() {
2781 return new SubMap<K,V>(m, lo, loInclusive,
2782 hi, hiInclusive, !isDescending);
2783 }
2784
2785 /* ---------------- Relational methods -------------- */
2786
2787 public Map.Entry<K,V> ceilingEntry(K key) {
2788 return getNearEntry(key, GT|EQ);
2789 }
2790
2791 public K ceilingKey(K key) {
2792 return getNearKey(key, GT|EQ);
2793 }
2794
2795 public Map.Entry<K,V> lowerEntry(K key) {
2796 return getNearEntry(key, LT);
2797 }
2798
2799 public K lowerKey(K key) {
2800 return getNearKey(key, LT);
2801 }
2802
2803 public Map.Entry<K,V> floorEntry(K key) {
2804 return getNearEntry(key, LT|EQ);
2805 }
2806
2807 public K floorKey(K key) {
2808 return getNearKey(key, LT|EQ);
2809 }
2810
2811 public Map.Entry<K,V> higherEntry(K key) {
2812 return getNearEntry(key, GT);
2813 }
2814
2815 public K higherKey(K key) {
2816 return getNearKey(key, GT);
2817 }
2818
2819 public K firstKey() {
2820 return isDescending ? highestKey() : lowestKey();
2821 }
2822
2823 public K lastKey() {
2824 return isDescending ? lowestKey() : highestKey();
2825 }
2826
2827 public Map.Entry<K,V> firstEntry() {
2828 return isDescending ? highestEntry() : lowestEntry();
2829 }
2830
2831 public Map.Entry<K,V> lastEntry() {
2832 return isDescending ? lowestEntry() : highestEntry();
2833 }
2834
2835 public Map.Entry<K,V> pollFirstEntry() {
2836 return isDescending ? removeHighest() : removeLowest();
2837 }
2838
2839 public Map.Entry<K,V> pollLastEntry() {
2840 return isDescending ? removeLowest() : removeHighest();
2841 }
2842
2843 /* ---------------- Submap Views -------------- */
2844
2845 public NavigableSet<K> keySet() {
2846 KeySet<K,V> ks;
2847 if ((ks = keySetView) != null) return ks;
2848 return keySetView = new KeySet<>(this);
2849 }
2850
2851 public NavigableSet<K> navigableKeySet() {
2852 KeySet<K,V> ks;
2853 if ((ks = keySetView) != null) return ks;
2854 return keySetView = new KeySet<>(this);
2855 }
2856
2857 public Collection<V> values() {
2858 Values<K,V> vs;
2859 if ((vs = valuesView) != null) return vs;
2860 return valuesView = new Values<>(this);
2861 }
2862
2863 public Set<Map.Entry<K,V>> entrySet() {
2864 EntrySet<K,V> es;
2865 if ((es = entrySetView) != null) return es;
2866 return entrySetView = new EntrySet<K,V>(this);
2867 }
2868
2869 public NavigableSet<K> descendingKeySet() {
2870 return descendingMap().navigableKeySet();
2871 }
2872
2873 /**
2874 * Variant of main Iter class to traverse through submaps.
2875 * Also serves as back-up Spliterator for views.
2876 */
2877 abstract class SubMapIter<T> implements Iterator<T>, Spliterator<T> {
2878 /** the last node returned by next() */
2879 Node<K,V> lastReturned;
2880 /** the next node to return from next(); */
2881 Node<K,V> next;
2882 /** Cache of next value field to maintain weak consistency */
2883 V nextValue;
2884
2885 SubMapIter() {
2886 VarHandle.acquireFence();
2887 Comparator<? super K> cmp = m.comparator;
2888 for (;;) {
2889 next = isDescending ? hiNode(cmp) : loNode(cmp);
2890 if (next == null)
2891 break;
2892 V x = next.val;
2893 if (x != null) {
2894 if (! inBounds(next.key, cmp))
2895 next = null;
2896 else
2897 nextValue = x;
2898 break;
2899 }
2900 }
2901 }
2902
2903 public final boolean hasNext() {
2904 return next != null;
2905 }
2906
2907 final void advance() {
2908 if (next == null)
2909 throw new NoSuchElementException();
2910 lastReturned = next;
2911 if (isDescending)
2912 descend();
2913 else
2914 ascend();
2915 }
2916
2917 private void ascend() {
2918 Comparator<? super K> cmp = m.comparator;
2919 for (;;) {
2920 next = next.next;
2921 if (next == null)
2922 break;
2923 V x = next.val;
2924 if (x != null) {
2925 if (tooHigh(next.key, cmp))
2926 next = null;
2927 else
2928 nextValue = x;
2929 break;
2930 }
2931 }
2932 }
2933
2934 private void descend() {
2935 Comparator<? super K> cmp = m.comparator;
2936 for (;;) {
2937 next = m.findNear(lastReturned.key, LT, cmp);
2938 if (next == null)
2939 break;
2940 V x = next.val;
2941 if (x != null) {
2942 if (tooLow(next.key, cmp))
2943 next = null;
2944 else
2945 nextValue = x;
2946 break;
2947 }
2948 }
2949 }
2950
2951 public void remove() {
2952 Node<K,V> l = lastReturned;
2953 if (l == null)
2954 throw new IllegalStateException();
2955 m.remove(l.key);
2956 lastReturned = null;
2957 }
2958
2959 public Spliterator<T> trySplit() {
2960 return null;
2961 }
2962
2963 public boolean tryAdvance(Consumer<? super T> action) {
2964 if (hasNext()) {
2965 action.accept(next());
2966 return true;
2967 }
2968 return false;
2969 }
2970
2971 public void forEachRemaining(Consumer<? super T> action) {
2972 while (hasNext())
2973 action.accept(next());
2974 }
2975
2976 public long estimateSize() {
2977 return Long.MAX_VALUE;
2978 }
2979
2980 }
2981
2982 final class SubMapValueIterator extends SubMapIter<V> {
2983 public V next() {
2984 V v = nextValue;
2985 advance();
2986 return v;
2987 }
2988 public int characteristics() {
2989 return 0;
2990 }
2991 }
2992
2993 final class SubMapKeyIterator extends SubMapIter<K> {
2994 public K next() {
2995 Node<K,V> n = next;
2996 advance();
2997 return n.key;
2998 }
2999 public int characteristics() {
3000 return Spliterator.DISTINCT | Spliterator.ORDERED |
3001 Spliterator.SORTED;
3002 }
3003 public final Comparator<? super K> getComparator() {
3004 return SubMap.this.comparator();
3005 }
3006 }
3007
3008 final class SubMapEntryIterator extends SubMapIter<Map.Entry<K,V>> {
3009 public Map.Entry<K,V> next() {
3010 Node<K,V> n = next;
3011 V v = nextValue;
3012 advance();
3013 return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
3014 }
3015 public int characteristics() {
3016 return Spliterator.DISTINCT;
3017 }
3018 }
3019 }
3020
3021 // default Map method overrides
3022
3023 public void forEach(BiConsumer<? super K, ? super V> action) {
3024 if (action == null) throw new NullPointerException();
3025 Node<K,V> b, n; V v;
3026 if ((b = baseHead()) != null) {
3027 while ((n = b.next) != null) {
3028 if ((v = n.val) != null)
3029 action.accept(n.key, v);
3030 b = n;
3031 }
3032 }
3033 }
3034
3035 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
3036 if (function == null) throw new NullPointerException();
3037 Node<K,V> b, n; V v;
3038 if ((b = baseHead()) != null) {
3039 while ((n = b.next) != null) {
3040 while ((v = n.val) != null) {
3041 V r = function.apply(n.key, v);
3042 if (r == null) throw new NullPointerException();
3043 if (VAL.compareAndSet(n, v, r))
3044 break;
3045 }
3046 b = n;
3047 }
3048 }
3049 }
3050
3051 /**
3052 * Helper method for EntrySet.removeIf.
3053 */
3054 boolean removeEntryIf(Predicate<? super Entry<K,V>> function) {
3055 if (function == null) throw new NullPointerException();
3056 boolean removed = false;
3057 Node<K,V> b, n; V v;
3058 if ((b = baseHead()) != null) {
3059 while ((n = b.next) != null) {
3060 if ((v = n.val) != null) {
3061 K k = n.key;
3062 Map.Entry<K,V> e = new AbstractMap.SimpleImmutableEntry<>(k, v);
3063 if (function.test(e) && remove(k, v))
3064 removed = true;
3065 }
3066 b = n;
3067 }
3068 }
3069 return removed;
3070 }
3071
3072 /**
3073 * Helper method for Values.removeIf.
3074 */
3075 boolean removeValueIf(Predicate<? super V> function) {
3076 if (function == null) throw new NullPointerException();
3077 boolean removed = false;
3078 Node<K,V> b, n; V v;
3079 if ((b = baseHead()) != null) {
3080 while ((n = b.next) != null) {
3081 if ((v = n.val) != null && function.test(v) && remove(n.key, v))
3082 removed = true;
3083 b = n;
3084 }
3085 }
3086 return removed;
3087 }
3088
3089 /**
3090 * Base class providing common structure for Spliterators.
3091 * (Although not all that much common functionality; as usual for
3092 * view classes, details annoyingly vary in key, value, and entry
3093 * subclasses in ways that are not worth abstracting out for
3094 * internal classes.)
3095 *
3096 * The basic split strategy is to recursively descend from top
3097 * level, row by row, descending to next row when either split
3098 * off, or the end of row is encountered. Control of the number of
3099 * splits relies on some statistical estimation: The expected
3100 * remaining number of elements of a skip list when advancing
3101 * either across or down decreases by about 25%.
3102 */
3103 abstract static class CSLMSpliterator<K,V> {
3104 final Comparator<? super K> comparator;
3105 final K fence; // exclusive upper bound for keys, or null if to end
3106 Index<K,V> row; // the level to split out
3107 Node<K,V> current; // current traversal node; initialize at origin
3108 long est; // size estimate
3109 CSLMSpliterator(Comparator<? super K> comparator, Index<K,V> row,
3110 Node<K,V> origin, K fence, long est) {
3111 this.comparator = comparator; this.row = row;
3112 this.current = origin; this.fence = fence; this.est = est;
3113 }
3114
3115 public final long estimateSize() { return est; }
3116 }
3117
3118 static final class KeySpliterator<K,V> extends CSLMSpliterator<K,V>
3119 implements Spliterator<K> {
3120 KeySpliterator(Comparator<? super K> comparator, Index<K,V> row,
3121 Node<K,V> origin, K fence, long est) {
3122 super(comparator, row, origin, fence, est);
3123 }
3124
3125 public KeySpliterator<K,V> trySplit() {
3126 Node<K,V> e; K ek;
3127 Comparator<? super K> cmp = comparator;
3128 K f = fence;
3129 if ((e = current) != null && (ek = e.key) != null) {
3130 for (Index<K,V> q = row; q != null; q = row = q.down) {
3131 Index<K,V> s; Node<K,V> b, n; K sk;
3132 if ((s = q.right) != null && (b = s.node) != null &&
3133 (n = b.next) != null && n.val != null &&
3134 (sk = n.key) != null && cpr(cmp, sk, ek) > 0 &&
3135 (f == null || cpr(cmp, sk, f) < 0)) {
3136 current = n;
3137 Index<K,V> r = q.down;
3138 row = (s.right != null) ? s : s.down;
3139 est -= est >>> 2;
3140 return new KeySpliterator<K,V>(cmp, r, e, sk, est);
3141 }
3142 }
3143 }
3144 return null;
3145 }
3146
3147 public void forEachRemaining(Consumer<? super K> action) {
3148 if (action == null) throw new NullPointerException();
3149 Comparator<? super K> cmp = comparator;
3150 K f = fence;
3151 Node<K,V> e = current;
3152 current = null;
3153 for (; e != null; e = e.next) {
3154 K k;
3155 if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0)
3156 break;
3157 if (e.val != null)
3158 action.accept(k);
3159 }
3160 }
3161
3162 public boolean tryAdvance(Consumer<? super K> action) {
3163 if (action == null) throw new NullPointerException();
3164 Comparator<? super K> cmp = comparator;
3165 K f = fence;
3166 Node<K,V> e = current;
3167 for (; e != null; e = e.next) {
3168 K k;
3169 if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) {
3170 e = null;
3171 break;
3172 }
3173 if (e.val != null) {
3174 current = e.next;
3175 action.accept(k);
3176 return true;
3177 }
3178 }
3179 current = e;
3180 return false;
3181 }
3182
3183 public int characteristics() {
3184 return Spliterator.DISTINCT | Spliterator.SORTED |
3185 Spliterator.ORDERED | Spliterator.CONCURRENT |
3186 Spliterator.NONNULL;
3187 }
3188
3189 public final Comparator<? super K> getComparator() {
3190 return comparator;
3191 }
3192 }
3193 // factory method for KeySpliterator
3194 final KeySpliterator<K,V> keySpliterator() {
3195 Index<K,V> h; Node<K,V> n; long est;
3196 VarHandle.acquireFence();
3197 if ((h = head) == null) {
3198 n = null;
3199 est = 0L;
3200 }
3201 else {
3202 n = h.node;
3203 est = getAdderCount();
3204 }
3205 return new KeySpliterator<K,V>(comparator, h, n, null, est);
3206 }
3207
3208 static final class ValueSpliterator<K,V> extends CSLMSpliterator<K,V>
3209 implements Spliterator<V> {
3210 ValueSpliterator(Comparator<? super K> comparator, Index<K,V> row,
3211 Node<K,V> origin, K fence, long est) {
3212 super(comparator, row, origin, fence, est);
3213 }
3214
3215 public ValueSpliterator<K,V> trySplit() {
3216 Node<K,V> e; K ek;
3217 Comparator<? super K> cmp = comparator;
3218 K f = fence;
3219 if ((e = current) != null && (ek = e.key) != null) {
3220 for (Index<K,V> q = row; q != null; q = row = q.down) {
3221 Index<K,V> s; Node<K,V> b, n; K sk;
3222 if ((s = q.right) != null && (b = s.node) != null &&
3223 (n = b.next) != null && n.val != null &&
3224 (sk = n.key) != null && cpr(cmp, sk, ek) > 0 &&
3225 (f == null || cpr(cmp, sk, f) < 0)) {
3226 current = n;
3227 Index<K,V> r = q.down;
3228 row = (s.right != null) ? s : s.down;
3229 est -= est >>> 2;
3230 return new ValueSpliterator<K,V>(cmp, r, e, sk, est);
3231 }
3232 }
3233 }
3234 return null;
3235 }
3236
3237 public void forEachRemaining(Consumer<? super V> action) {
3238 if (action == null) throw new NullPointerException();
3239 Comparator<? super K> cmp = comparator;
3240 K f = fence;
3241 Node<K,V> e = current;
3242 current = null;
3243 for (; e != null; e = e.next) {
3244 K k; V v;
3245 if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0)
3246 break;
3247 if ((v = e.val) != null)
3248 action.accept(v);
3249 }
3250 }
3251
3252 public boolean tryAdvance(Consumer<? super V> action) {
3253 if (action == null) throw new NullPointerException();
3254 Comparator<? super K> cmp = comparator;
3255 K f = fence;
3256 Node<K,V> e = current;
3257 for (; e != null; e = e.next) {
3258 K k; V v;
3259 if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) {
3260 e = null;
3261 break;
3262 }
3263 if ((v = e.val) != null) {
3264 current = e.next;
3265 action.accept(v);
3266 return true;
3267 }
3268 }
3269 current = e;
3270 return false;
3271 }
3272
3273 public int characteristics() {
3274 return Spliterator.CONCURRENT | Spliterator.ORDERED |
3275 Spliterator.NONNULL;
3276 }
3277 }
3278
3279 // Almost the same as keySpliterator()
3280 final ValueSpliterator<K,V> valueSpliterator() {
3281 Index<K,V> h; Node<K,V> n; long est;
3282 VarHandle.acquireFence();
3283 if ((h = head) == null) {
3284 n = null;
3285 est = 0L;
3286 }
3287 else {
3288 n = h.node;
3289 est = getAdderCount();
3290 }
3291 return new ValueSpliterator<K,V>(comparator, h, n, null, est);
3292 }
3293
3294 static final class EntrySpliterator<K,V> extends CSLMSpliterator<K,V>
3295 implements Spliterator<Map.Entry<K,V>> {
3296 EntrySpliterator(Comparator<? super K> comparator, Index<K,V> row,
3297 Node<K,V> origin, K fence, long est) {
3298 super(comparator, row, origin, fence, est);
3299 }
3300
3301 public EntrySpliterator<K,V> trySplit() {
3302 Node<K,V> e; K ek;
3303 Comparator<? super K> cmp = comparator;
3304 K f = fence;
3305 if ((e = current) != null && (ek = e.key) != null) {
3306 for (Index<K,V> q = row; q != null; q = row = q.down) {
3307 Index<K,V> s; Node<K,V> b, n; K sk;
3308 if ((s = q.right) != null && (b = s.node) != null &&
3309 (n = b.next) != null && n.val != null &&
3310 (sk = n.key) != null && cpr(cmp, sk, ek) > 0 &&
3311 (f == null || cpr(cmp, sk, f) < 0)) {
3312 current = n;
3313 Index<K,V> r = q.down;
3314 row = (s.right != null) ? s : s.down;
3315 est -= est >>> 2;
3316 return new EntrySpliterator<K,V>(cmp, r, e, sk, est);
3317 }
3318 }
3319 }
3320 return null;
3321 }
3322
3323 public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
3324 if (action == null) throw new NullPointerException();
3325 Comparator<? super K> cmp = comparator;
3326 K f = fence;
3327 Node<K,V> e = current;
3328 current = null;
3329 for (; e != null; e = e.next) {
3330 K k; V v;
3331 if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0)
3332 break;
3333 if ((v = e.val) != null) {
3334 action.accept
3335 (new AbstractMap.SimpleImmutableEntry<K,V>(k, v));
3336 }
3337 }
3338 }
3339
3340 public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
3341 if (action == null) throw new NullPointerException();
3342 Comparator<? super K> cmp = comparator;
3343 K f = fence;
3344 Node<K,V> e = current;
3345 for (; e != null; e = e.next) {
3346 K k; V v;
3347 if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) {
3348 e = null;
3349 break;
3350 }
3351 if ((v = e.val) != null) {
3352 current = e.next;
3353 action.accept
3354 (new AbstractMap.SimpleImmutableEntry<K,V>(k, v));
3355 return true;
3356 }
3357 }
3358 current = e;
3359 return false;
3360 }
3361
3362 public int characteristics() {
3363 return Spliterator.DISTINCT | Spliterator.SORTED |
3364 Spliterator.ORDERED | Spliterator.CONCURRENT |
3365 Spliterator.NONNULL;
3366 }
3367
3368 public final Comparator<Map.Entry<K,V>> getComparator() {
3369 // Adapt or create a key-based comparator
3370 if (comparator != null) {
3371 return Map.Entry.comparingByKey(comparator);
3372 }
3373 else {
3374 return (Comparator<Map.Entry<K,V>> & Serializable) (e1, e2) -> {
3375 @SuppressWarnings("unchecked")
3376 Comparable<? super K> k1 = (Comparable<? super K>) e1.getKey();
3377 return k1.compareTo(e2.getKey());
3378 };
3379 }
3380 }
3381 }
3382
3383 // Almost the same as keySpliterator()
3384 final EntrySpliterator<K,V> entrySpliterator() {
3385 Index<K,V> h; Node<K,V> n; long est;
3386 VarHandle.acquireFence();
3387 if ((h = head) == null) {
3388 n = null;
3389 est = 0L;
3390 }
3391 else {
3392 n = h.node;
3393 est = getAdderCount();
3394 }
3395 return new EntrySpliterator<K,V>(comparator, h, n, null, est);
3396 }
3397
3398 // VarHandle mechanics
3399 private static final VarHandle HEAD;
3400 private static final VarHandle ADDER;
3401 private static final VarHandle NEXT;
3402 private static final VarHandle VAL;
3403 private static final VarHandle RIGHT;
3404 static {
3405 try {
3406 MethodHandles.Lookup l = MethodHandles.lookup();
3407 HEAD = l.findVarHandle(ConcurrentSkipListMap.class, "head",
3408 Index.class);
3409 ADDER = l.findVarHandle(ConcurrentSkipListMap.class, "adder",
3410 LongAdder.class);
3411 NEXT = l.findVarHandle(Node.class, "next", Node.class);
3412 VAL = l.findVarHandle(Node.class, "val", Object.class);
3413 RIGHT = l.findVarHandle(Index.class, "right", Index.class);
3414 } catch (ReflectiveOperationException e) {
3415 throw new Error(e);
3416 }
3417 }
3418 }