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