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