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.util.*;

  38 
  39 /**
  40  * A scalable concurrent {@link ConcurrentNavigableMap} implementation.
  41  * The map is sorted according to the {@linkplain Comparable natural
  42  * ordering} of its keys, or by a {@link Comparator} provided at map
  43  * creation time, depending on which constructor is used.
  44  *
  45  * <p>This class implements a concurrent variant of <a
  46  * href="http://en.wikipedia.org/wiki/Skip_list" target="_top">SkipLists</a>
  47  * providing expected average <i>log(n)</i> time cost for the
  48  * <tt>containsKey</tt>, <tt>get</tt>, <tt>put</tt> and
  49  * <tt>remove</tt> operations and their variants.  Insertion, removal,
  50  * update, and access operations safely execute concurrently by
  51  * multiple threads.  Iterators are <i>weakly consistent</i>, returning
  52  * elements reflecting the state of the map at some point at or since
  53  * the creation of the iterator.  They do <em>not</em> throw {@link
  54  * ConcurrentModificationException}, and may proceed concurrently with
  55  * other operations. Ascending key ordered views and their iterators
  56  * are faster than descending ones.
  57  *
  58  * <p>All <tt>Map.Entry</tt> pairs returned by methods in this class
  59  * and its views represent snapshots of mappings at the time they were
  60  * produced. They do <em>not</em> support the <tt>Entry.setValue</tt>
  61  * method. (Note however that it is possible to change mappings in the
  62  * associated map using <tt>put</tt>, <tt>putIfAbsent</tt>, or
  63  * <tt>replace</tt>, depending on exactly which effect you need.)
  64  *
  65  * <p>Beware that, unlike in most collections, the <tt>size</tt>
  66  * method is <em>not</em> a constant-time operation. Because of the
  67  * asynchronous nature of these maps, determining the current number
  68  * of elements requires a traversal of the elements, and so may report
  69  * inaccurate results if this collection is modified during traversal.
  70  * Additionally, the bulk operations <tt>putAll</tt>, <tt>equals</tt>,
  71  * <tt>toArray</tt>, <tt>containsValue</tt>, and <tt>clear</tt> are
  72  * <em>not</em> guaranteed to be performed atomically. For example, an
  73  * iterator operating concurrently with a <tt>putAll</tt> operation
  74  * might view only some of the added elements.
  75  *
  76  * <p>This class and its views and iterators implement all of the
  77  * <em>optional</em> methods of the {@link Map} and {@link Iterator}
  78  * interfaces. Like most other concurrent collections, this class does
  79  * <em>not</em> permit the use of <tt>null</tt> keys or values because some
  80  * null return values cannot be reliably distinguished from the absence of
  81  * elements.
  82  *
  83  * <p>This class is a member of the
  84  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  85  * Java Collections Framework</a>.
  86  *
  87  * @author Doug Lea
  88  * @param <K> the type of keys maintained by this map
  89  * @param <V> the type of mapped values
  90  * @since 1.6
  91  */
  92 @SuppressWarnings("unchecked")
  93 public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
  94     implements ConcurrentNavigableMap<K,V>,
  95                Cloneable,
  96                java.io.Serializable {
  97     /*
  98      * This class implements a tree-like two-dimensionally linked skip
  99      * list in which the index levels are represented in separate
 100      * nodes from the base nodes holding data.  There are two reasons
 101      * for taking this approach instead of the usual array-based
 102      * structure: 1) Array based implementations seem to encounter
 103      * more complexity and overhead 2) We can use cheaper algorithms
 104      * for the heavily-traversed index lists than can be used for the
 105      * base lists.  Here's a picture of some of the basics for a
 106      * possible list with 2 levels of index:
 107      *
 108      * Head nodes          Index nodes
 109      * +-+    right        +-+                      +-+
 110      * |2|---------------->| |--------------------->| |->null
 111      * +-+                 +-+                      +-+
 112      *  | down              |                        |
 113      *  v                   v                        v
 114      * +-+            +-+  +-+       +-+            +-+       +-+
 115      * |1|----------->| |->| |------>| |----------->| |------>| |->null
 116      * +-+            +-+  +-+       +-+            +-+       +-+
 117      *  v              |    |         |              |         |
 118      * Nodes  next     v    v         v              v         v
 119      * +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
 120      * | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null
 121      * +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
 122      *
 123      * The base lists use a variant of the HM linked ordered set
 124      * algorithm. See Tim Harris, "A pragmatic implementation of
 125      * non-blocking linked lists"
 126      * http://www.cl.cam.ac.uk/~tlh20/publications.html and Maged
 127      * Michael "High Performance Dynamic Lock-Free Hash Tables and
 128      * List-Based Sets"
 129      * http://www.research.ibm.com/people/m/michael/pubs.htm.  The
 130      * basic idea in these lists is to mark the "next" pointers of
 131      * deleted nodes when deleting to avoid conflicts with concurrent
 132      * insertions, and when traversing to keep track of triples
 133      * (predecessor, node, successor) in order to detect when and how
 134      * to unlink these deleted nodes.
 135      *
 136      * Rather than using mark-bits to mark list deletions (which can
 137      * be slow and space-intensive using AtomicMarkedReference), nodes
 138      * use direct CAS'able next pointers.  On deletion, instead of
 139      * marking a pointer, they splice in another node that can be
 140      * thought of as standing for a marked pointer (indicating this by
 141      * using otherwise impossible field values).  Using plain nodes
 142      * acts roughly like "boxed" implementations of marked pointers,
 143      * but uses new nodes only when nodes are deleted, not for every
 144      * link.  This requires less space and supports faster
 145      * traversal. Even if marked references were better supported by
 146      * JVMs, traversal using this technique might still be faster
 147      * because any search need only read ahead one more node than
 148      * otherwise required (to check for trailing marker) rather than
 149      * unmasking mark bits or whatever on each read.
 150      *
 151      * This approach maintains the essential property needed in the HM
 152      * algorithm of changing the next-pointer of a deleted node so
 153      * that any other CAS of it will fail, but implements the idea by
 154      * changing the pointer to point to a different node, not by
 155      * marking it.  While it would be possible to further squeeze
 156      * space by defining marker nodes not to have key/value fields, it
 157      * isn't worth the extra type-testing overhead.  The deletion
 158      * markers are rarely encountered during traversal and are
 159      * normally quickly garbage collected. (Note that this technique
 160      * would not work well in systems without garbage collection.)
 161      *
 162      * In addition to using deletion markers, the lists also use
 163      * nullness of value fields to indicate deletion, in a style
 164      * similar to typical lazy-deletion schemes.  If a node's value is
 165      * null, then it is considered logically deleted and ignored even
 166      * though it is still reachable. This maintains proper control of
 167      * concurrent replace vs delete operations -- an attempted replace
 168      * must fail if a delete beat it by nulling field, and a delete
 169      * must return the last non-null value held in the field. (Note:
 170      * Null, rather than some special marker, is used for value fields
 171      * here because it just so happens to mesh with the Map API
 172      * requirement that method get returns null if there is no
 173      * mapping, which allows nodes to remain concurrently readable
 174      * even when deleted. Using any other marker value here would be
 175      * messy at best.)
 176      *
 177      * Here's the sequence of events for a deletion of node n with
 178      * predecessor b and successor f, initially:
 179      *
 180      *        +------+       +------+      +------+
 181      *   ...  |   b  |------>|   n  |----->|   f  | ...
 182      *        +------+       +------+      +------+
 183      *
 184      * 1. CAS n's value field from non-null to null.
 185      *    From this point on, no public operations encountering
 186      *    the node consider this mapping to exist. However, other
 187      *    ongoing insertions and deletions might still modify
 188      *    n's next pointer.
 189      *
 190      * 2. CAS n's next pointer to point to a new marker node.
 191      *    From this point on, no other nodes can be appended to n.
 192      *    which avoids deletion errors in CAS-based linked lists.
 193      *
 194      *        +------+       +------+      +------+       +------+
 195      *   ...  |   b  |------>|   n  |----->|marker|------>|   f  | ...
 196      *        +------+       +------+      +------+       +------+
 197      *
 198      * 3. CAS b's next pointer over both n and its marker.
 199      *    From this point on, no new traversals will encounter n,
 200      *    and it can eventually be GCed.
 201      *        +------+                                    +------+
 202      *   ...  |   b  |----------------------------------->|   f  | ...
 203      *        +------+                                    +------+
 204      *
 205      * A failure at step 1 leads to simple retry due to a lost race
 206      * with another operation. Steps 2-3 can fail because some other
 207      * thread noticed during a traversal a node with null value and
 208      * helped out by marking and/or unlinking.  This helping-out
 209      * ensures that no thread can become stuck waiting for progress of
 210      * the deleting thread.  The use of marker nodes slightly
 211      * complicates helping-out code because traversals must track
 212      * consistent reads of up to four nodes (b, n, marker, f), not
 213      * just (b, n, f), although the next field of a marker is
 214      * immutable, and once a next field is CAS'ed to point to a
 215      * marker, it never again changes, so this requires less care.
 216      *
 217      * Skip lists add indexing to this scheme, so that the base-level
 218      * traversals start close to the locations being found, inserted
 219      * or deleted -- usually base level traversals only traverse a few
 220      * nodes. This doesn't change the basic algorithm except for the
 221      * need to make sure base traversals start at predecessors (here,
 222      * b) that are not (structurally) deleted, otherwise retrying
 223      * after processing the deletion.
 224      *
 225      * Index levels are maintained as lists with volatile next fields,
 226      * using CAS to link and unlink.  Races are allowed in index-list
 227      * operations that can (rarely) fail to link in a new index node
 228      * or delete one. (We can't do this of course for data nodes.)
 229      * However, even when this happens, the index lists remain sorted,
 230      * so correctly serve as indices.  This can impact performance,
 231      * but since skip lists are probabilistic anyway, the net result
 232      * is that under contention, the effective "p" value may be lower
 233      * than its nominal value. And race windows are kept small enough
 234      * that in practice these failures are rare, even under a lot of
 235      * contention.
 236      *
 237      * The fact that retries (for both base and index lists) are
 238      * relatively cheap due to indexing allows some minor
 239      * simplifications of retry logic. Traversal restarts are
 240      * performed after most "helping-out" CASes. This isn't always
 241      * strictly necessary, but the implicit backoffs tend to help
 242      * reduce other downstream failed CAS's enough to outweigh restart
 243      * cost.  This worsens the worst case, but seems to improve even
 244      * highly contended cases.
 245      *
 246      * Unlike most skip-list implementations, index insertion and
 247      * deletion here require a separate traversal pass occuring after
 248      * the base-level action, to add or remove index nodes.  This adds
 249      * to single-threaded overhead, but improves contended
 250      * multithreaded performance by narrowing interference windows,
 251      * and allows deletion to ensure that all index nodes will be made
 252      * unreachable upon return from a public remove operation, thus
 253      * avoiding unwanted garbage retention. This is more important
 254      * here than in some other data structures because we cannot null
 255      * out node fields referencing user keys since they might still be
 256      * read by other ongoing traversals.
 257      *
 258      * Indexing uses skip list parameters that maintain good search
 259      * performance while using sparser-than-usual indices: The
 260      * hardwired parameters k=1, p=0.5 (see method randomLevel) mean
 261      * that about one-quarter of the nodes have indices. Of those that
 262      * do, half have one level, a quarter have two, and so on (see
 263      * Pugh's Skip List Cookbook, sec 3.4).  The expected total space
 264      * requirement for a map is slightly less than for the current
 265      * implementation of java.util.TreeMap.
 266      *
 267      * Changing the level of the index (i.e, the height of the
 268      * tree-like structure) also uses CAS. The head index has initial
 269      * level/height of one. Creation of an index with height greater
 270      * than the current level adds a level to the head index by
 271      * CAS'ing on a new top-most head. To maintain good performance
 272      * after a lot of removals, deletion methods heuristically try to
 273      * reduce the height if the topmost levels appear to be empty.
 274      * This may encounter races in which it possible (but rare) to
 275      * reduce and "lose" a level just as it is about to contain an
 276      * index (that will then never be encountered). This does no
 277      * structural harm, and in practice appears to be a better option
 278      * than allowing unrestrained growth of levels.
 279      *
 280      * The code for all this is more verbose than you'd like. Most
 281      * operations entail locating an element (or position to insert an
 282      * element). The code to do this can't be nicely factored out
 283      * because subsequent uses require a snapshot of predecessor
 284      * and/or successor and/or value fields which can't be returned
 285      * all at once, at least not without creating yet another object
 286      * to hold them -- creating such little objects is an especially
 287      * bad idea for basic internal search operations because it adds
 288      * to GC overhead.  (This is one of the few times I've wished Java
 289      * had macros.) Instead, some traversal code is interleaved within
 290      * insertion and removal operations.  The control logic to handle
 291      * all the retry conditions is sometimes twisty. Most search is
 292      * broken into 2 parts. findPredecessor() searches index nodes
 293      * only, returning a base-level predecessor of the key. findNode()
 294      * finishes out the base-level search. Even with this factoring,
 295      * there is a fair amount of near-duplication of code to handle
 296      * variants.
 297      *
 298      * For explanation of algorithms sharing at least a couple of
 299      * features with this one, see Mikhail Fomitchev's thesis
 300      * (http://www.cs.yorku.ca/~mikhail/), Keir Fraser's thesis
 301      * (http://www.cl.cam.ac.uk/users/kaf24/), and Hakan Sundell's
 302      * thesis (http://www.cs.chalmers.se/~phs/).
 303      *
 304      * Given the use of tree-like index nodes, you might wonder why
 305      * this doesn't use some kind of search tree instead, which would
 306      * support somewhat faster search operations. The reason is that
 307      * there are no known efficient lock-free insertion and deletion
 308      * algorithms for search trees. The immutability of the "down"
 309      * links of index nodes (as opposed to mutable "left" fields in
 310      * true trees) makes this tractable using only CAS operations.
 311      *
 312      * Notation guide for local variables
 313      * Node:         b, n, f    for  predecessor, node, successor
 314      * Index:        q, r, d    for index node, right, down.
 315      *               t          for another index node
 316      * Head:         h
 317      * Levels:       j
 318      * Keys:         k, key
 319      * Values:       v, value
 320      * Comparisons:  c
 321      */
 322 
 323     private static final long serialVersionUID = -8627078645895051609L;
 324 
 325     /**
 326      * Generates the initial random seed for the cheaper per-instance
 327      * random number generators used in randomLevel.
 328      */
 329     private static final Random seedGenerator = new Random();
 330 
 331     /**
 332      * Special value used to identify base-level header
 333      */
 334     private static final Object BASE_HEADER = new Object();
 335 
 336     /**
 337      * The topmost head index of the skiplist.
 338      */
 339     private transient volatile HeadIndex<K,V> head;
 340 
 341     /**
 342      * The comparator used to maintain order in this map, or null
 343      * if using natural ordering.
 344      * @serial
 345      */
 346     private final Comparator<? super K> comparator;
 347 
 348     /**
 349      * Seed for simple random number generator.  Not volatile since it
 350      * doesn't matter too much if different threads don't see updates.
 351      */
 352     private transient int randomSeed;
 353 
 354     /** Lazily initialized key set */
 355     private transient KeySet<K> keySet;
 356     /** Lazily initialized entry set */
 357     private transient EntrySet<K,V> entrySet;
 358     /** Lazily initialized values collection */
 359     private transient Values<V> values;
 360     /** Lazily initialized descending key set */
 361     private transient ConcurrentNavigableMap<K,V> descendingMap;
 362 
 363     /**
 364      * Initializes or resets state. Needed by constructors, clone,
 365      * clear, readObject. and ConcurrentSkipListSet.clone.
 366      * (Note that comparator must be separately initialized.)
 367      */
 368     final void initialize() {
 369         keySet = null;
 370         entrySet = null;
 371         values = null;
 372         descendingMap = null;
 373         randomSeed = seedGenerator.nextInt() | 0x0100; // ensure nonzero
 374         head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),
 375                                   null, null, 1);
 376     }
 377 
 378     /**
 379      * compareAndSet head node
 380      */
 381     private boolean casHead(HeadIndex<K,V> cmp, HeadIndex<K,V> val) {
 382         return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val);
 383     }
 384 
 385     /* ---------------- Nodes -------------- */
 386 
 387     /**
 388      * Nodes hold keys and values, and are singly linked in sorted
 389      * order, possibly with some intervening marker nodes. The list is
 390      * headed by a dummy node accessible as head.node. The value field
 391      * is declared only as Object because it takes special non-V
 392      * values for marker and header nodes.
 393      */
 394     static final class Node<K,V> {
 395         final K key;
 396         volatile Object value;
 397         volatile Node<K,V> next;
 398 
 399         /**
 400          * Creates a new regular node.
 401          */
 402         Node(K key, Object value, Node<K,V> next) {
 403             this.key = key;
 404             this.value = value;
 405             this.next = next;
 406         }
 407 
 408         /**
 409          * Creates a new marker node. A marker is distinguished by
 410          * having its value field point to itself.  Marker nodes also
 411          * have null keys, a fact that is exploited in a few places,
 412          * but this doesn't distinguish markers from the base-level
 413          * header node (head.node), which also has a null key.
 414          */
 415         Node(Node<K,V> next) {
 416             this.key = null;
 417             this.value = this;
 418             this.next = next;
 419         }
 420 
 421         /**
 422          * compareAndSet value field
 423          */
 424         boolean casValue(Object cmp, Object val) {
 425             return UNSAFE.compareAndSwapObject(this, valueOffset, cmp, val);
 426         }
 427 
 428         /**
 429          * compareAndSet next field
 430          */
 431         boolean casNext(Node<K,V> cmp, Node<K,V> val) {
 432             return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
 433         }
 434 
 435         /**
 436          * Returns true if this node is a marker. This method isn't
 437          * actually called in any current code checking for markers
 438          * because callers will have already read value field and need
 439          * to use that read (not another done here) and so directly
 440          * test if value points to node.
 441          * @param n a possibly null reference to a node
 442          * @return true if this node is a marker node
 443          */
 444         boolean isMarker() {
 445             return value == this;
 446         }
 447 
 448         /**
 449          * Returns true if this node is the header of base-level list.
 450          * @return true if this node is header node
 451          */
 452         boolean isBaseHeader() {
 453             return value == BASE_HEADER;
 454         }
 455 
 456         /**
 457          * Tries to append a deletion marker to this node.
 458          * @param f the assumed current successor of this node
 459          * @return true if successful
 460          */
 461         boolean appendMarker(Node<K,V> f) {
 462             return casNext(f, new Node<K,V>(f));
 463         }
 464 
 465         /**
 466          * Helps out a deletion by appending marker or unlinking from
 467          * predecessor. This is called during traversals when value
 468          * field seen to be null.
 469          * @param b predecessor
 470          * @param f successor
 471          */
 472         void helpDelete(Node<K,V> b, Node<K,V> f) {
 473             /*
 474              * Rechecking links and then doing only one of the
 475              * help-out stages per call tends to minimize CAS
 476              * interference among helping threads.
 477              */
 478             if (f == next && this == b.next) {
 479                 if (f == null || f.value != f) // not already marked
 480                     appendMarker(f);
 481                 else
 482                     b.casNext(this, f.next);
 483             }
 484         }
 485 
 486         /**
 487          * Returns value if this node contains a valid key-value pair,
 488          * else null.
 489          * @return this node's value if it isn't a marker or header or
 490          * is deleted, else null.
 491          */
 492         V getValidValue() {
 493             Object v = value;
 494             if (v == this || v == BASE_HEADER)
 495                 return null;
 496             return (V)v;
 497         }
 498 
 499         /**
 500          * Creates and returns a new SimpleImmutableEntry holding current
 501          * mapping if this node holds a valid value, else null.
 502          * @return new entry or null
 503          */
 504         AbstractMap.SimpleImmutableEntry<K,V> createSnapshot() {
 505             V v = getValidValue();
 506             if (v == null)
 507                 return null;
 508             return new AbstractMap.SimpleImmutableEntry<K,V>(key, v);
 509         }
 510 
 511         // UNSAFE mechanics
 512 
 513         private static final sun.misc.Unsafe UNSAFE;
 514         private static final long valueOffset;
 515         private static final long nextOffset;
 516 
 517         static {
 518             try {
 519                 UNSAFE = sun.misc.Unsafe.getUnsafe();
 520                 Class<?> k = Node.class;
 521                 valueOffset = UNSAFE.objectFieldOffset
 522                     (k.getDeclaredField("value"));
 523                 nextOffset = UNSAFE.objectFieldOffset
 524                     (k.getDeclaredField("next"));
 525             } catch (Exception e) {
 526                 throw new Error(e);
 527             }
 528         }
 529     }
 530 
 531     /* ---------------- Indexing -------------- */
 532 
 533     /**
 534      * Index nodes represent the levels of the skip list.  Note that
 535      * even though both Nodes and Indexes have forward-pointing
 536      * fields, they have different types and are handled in different
 537      * ways, that can't nicely be captured by placing field in a
 538      * shared abstract class.
 539      */
 540     static class Index<K,V> {
 541         final Node<K,V> node;
 542         final Index<K,V> down;
 543         volatile Index<K,V> right;
 544 
 545         /**
 546          * Creates index node with given values.
 547          */
 548         Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
 549             this.node = node;
 550             this.down = down;
 551             this.right = right;
 552         }
 553 
 554         /**
 555          * compareAndSet right field
 556          */
 557         final boolean casRight(Index<K,V> cmp, Index<K,V> val) {
 558             return UNSAFE.compareAndSwapObject(this, rightOffset, cmp, val);
 559         }
 560 
 561         /**
 562          * Returns true if the node this indexes has been deleted.
 563          * @return true if indexed node is known to be deleted
 564          */
 565         final boolean indexesDeletedNode() {
 566             return node.value == null;
 567         }
 568 
 569         /**
 570          * Tries to CAS newSucc as successor.  To minimize races with
 571          * unlink that may lose this index node, if the node being
 572          * indexed is known to be deleted, it doesn't try to link in.
 573          * @param succ the expected current successor
 574          * @param newSucc the new successor
 575          * @return true if successful
 576          */
 577         final boolean link(Index<K,V> succ, Index<K,V> newSucc) {
 578             Node<K,V> n = node;
 579             newSucc.right = succ;
 580             return n.value != null && casRight(succ, newSucc);
 581         }
 582 
 583         /**
 584          * Tries to CAS right field to skip over apparent successor
 585          * succ.  Fails (forcing a retraversal by caller) if this node
 586          * is known to be deleted.
 587          * @param succ the expected current successor
 588          * @return true if successful
 589          */
 590         final boolean unlink(Index<K,V> succ) {
 591             return !indexesDeletedNode() && casRight(succ, succ.right);
 592         }
 593 
 594         // Unsafe mechanics
 595         private static final sun.misc.Unsafe UNSAFE;
 596         private static final long rightOffset;
 597         static {
 598             try {
 599                 UNSAFE = sun.misc.Unsafe.getUnsafe();
 600                 Class<?> k = Index.class;
 601                 rightOffset = UNSAFE.objectFieldOffset
 602                     (k.getDeclaredField("right"));
 603             } catch (Exception e) {
 604                 throw new Error(e);
 605             }
 606         }
 607     }
 608 
 609     /* ---------------- Head nodes -------------- */
 610 
 611     /**
 612      * Nodes heading each level keep track of their level.
 613      */
 614     static final class HeadIndex<K,V> extends Index<K,V> {
 615         final int level;
 616         HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {
 617             super(node, down, right);
 618             this.level = level;
 619         }
 620     }
 621 
 622     /* ---------------- Comparison utilities -------------- */
 623 
 624     /**
 625      * Represents a key with a comparator as a Comparable.
 626      *
 627      * Because most sorted collections seem to use natural ordering on
 628      * Comparables (Strings, Integers, etc), most internal methods are
 629      * geared to use them. This is generally faster than checking
 630      * per-comparison whether to use comparator or comparable because
 631      * it doesn't require a (Comparable) cast for each comparison.
 632      * (Optimizers can only sometimes remove such redundant checks
 633      * themselves.) When Comparators are used,
 634      * ComparableUsingComparators are created so that they act in the
 635      * same way as natural orderings. This penalizes use of
 636      * Comparators vs Comparables, which seems like the right
 637      * tradeoff.
 638      */
 639     static final class ComparableUsingComparator<K> implements Comparable<K> {
 640         final K actualKey;
 641         final Comparator<? super K> cmp;
 642         ComparableUsingComparator(K key, Comparator<? super K> cmp) {
 643             this.actualKey = key;
 644             this.cmp = cmp;
 645         }
 646         public int compareTo(K k2) {
 647             return cmp.compare(actualKey, k2);
 648         }
 649     }
 650 
 651     /**
 652      * If using comparator, return a ComparableUsingComparator, else
 653      * cast key as Comparable, which may cause ClassCastException,
 654      * which is propagated back to caller.
 655      */
 656     private Comparable<? super K> comparable(Object key)
 657             throws ClassCastException {
 658         if (key == null)
 659             throw new NullPointerException();
 660         if (comparator != null)
 661             return new ComparableUsingComparator<K>((K)key, comparator);
 662         else
 663             return (Comparable<? super K>)key;
 664     }
 665 
 666     /**
 667      * Compares using comparator or natural ordering. Used when the
 668      * ComparableUsingComparator approach doesn't apply.
 669      */
 670     int compare(K k1, K k2) throws ClassCastException {
 671         Comparator<? super K> cmp = comparator;
 672         if (cmp != null)
 673             return cmp.compare(k1, k2);
 674         else
 675             return ((Comparable<? super K>)k1).compareTo(k2);
 676     }
 677 
 678     /**
 679      * Returns true if given key greater than or equal to least and
 680      * strictly less than fence, bypassing either test if least or
 681      * fence are null. Needed mainly in submap operations.
 682      */
 683     boolean inHalfOpenRange(K key, K least, K fence) {
 684         if (key == null)
 685             throw new NullPointerException();
 686         return ((least == null || compare(key, least) >= 0) &&
 687                 (fence == null || compare(key, fence) <  0));
 688     }
 689 
 690     /**
 691      * Returns true if given key greater than or equal to least and less
 692      * or equal to fence. Needed mainly in submap operations.
 693      */
 694     boolean inOpenRange(K key, K least, K fence) {
 695         if (key == null)
 696             throw new NullPointerException();
 697         return ((least == null || compare(key, least) >= 0) &&
 698                 (fence == null || compare(key, fence) <= 0));
 699     }
 700 
 701     /* ---------------- Traversal -------------- */
 702 
 703     /**
 704      * Returns a base-level node with key strictly less than given key,
 705      * or the base-level header if there is no such node.  Also
 706      * unlinks indexes to deleted nodes found along the way.  Callers
 707      * rely on this side-effect of clearing indices to deleted nodes.
 708      * @param key the key
 709      * @return a predecessor of key
 710      */
 711     private Node<K,V> findPredecessor(Comparable<? super K> key) {
 712         if (key == null)
 713             throw new NullPointerException(); // don't postpone errors
 714         for (;;) {
 715             Index<K,V> q = head;
 716             Index<K,V> r = q.right;
 717             for (;;) {
 718                 if (r != null) {
 719                     Node<K,V> n = r.node;
 720                     K k = n.key;
 721                     if (n.value == null) {
 722                         if (!q.unlink(r))
 723                             break;           // restart
 724                         r = q.right;         // reread r
 725                         continue;
 726                     }
 727                     if (key.compareTo(k) > 0) {
 728                         q = r;
 729                         r = r.right;
 730                         continue;
 731                     }
 732                 }
 733                 Index<K,V> d = q.down;
 734                 if (d != null) {
 735                     q = d;
 736                     r = d.right;
 737                 } else
 738                     return q.node;
 739             }
 740         }
 741     }
 742 
 743     /**
 744      * Returns node holding key or null if no such, clearing out any
 745      * deleted nodes seen along the way.  Repeatedly traverses at
 746      * base-level looking for key starting at predecessor returned
 747      * from findPredecessor, processing base-level deletions as
 748      * encountered. Some callers rely on this side-effect of clearing
 749      * deleted nodes.
 750      *
 751      * Restarts occur, at traversal step centered on node n, if:
 752      *
 753      *   (1) After reading n's next field, n is no longer assumed
 754      *       predecessor b's current successor, which means that
 755      *       we don't have a consistent 3-node snapshot and so cannot
 756      *       unlink any subsequent deleted nodes encountered.
 757      *
 758      *   (2) n's value field is null, indicating n is deleted, in
 759      *       which case we help out an ongoing structural deletion
 760      *       before retrying.  Even though there are cases where such
 761      *       unlinking doesn't require restart, they aren't sorted out
 762      *       here because doing so would not usually outweigh cost of
 763      *       restarting.
 764      *
 765      *   (3) n is a marker or n's predecessor's value field is null,
 766      *       indicating (among other possibilities) that
 767      *       findPredecessor returned a deleted node. We can't unlink
 768      *       the node because we don't know its predecessor, so rely
 769      *       on another call to findPredecessor to notice and return
 770      *       some earlier predecessor, which it will do. This check is
 771      *       only strictly needed at beginning of loop, (and the
 772      *       b.value check isn't strictly needed at all) but is done
 773      *       each iteration to help avoid contention with other
 774      *       threads by callers that will fail to be able to change
 775      *       links, and so will retry anyway.
 776      *
 777      * The traversal loops in doPut, doRemove, and findNear all
 778      * include the same three kinds of checks. And specialized
 779      * versions appear in findFirst, and findLast and their
 780      * variants. They can't easily share code because each uses the
 781      * reads of fields held in locals occurring in the orders they
 782      * were performed.
 783      *
 784      * @param key the key
 785      * @return node holding key, or null if no such
 786      */
 787     private Node<K,V> findNode(Comparable<? super K> key) {
 788         for (;;) {
 789             Node<K,V> b = findPredecessor(key);
 790             Node<K,V> n = b.next;
 791             for (;;) {
 792                 if (n == null)
 793                     return null;
 794                 Node<K,V> f = n.next;
 795                 if (n != b.next)                // inconsistent read
 796                     break;
 797                 Object v = n.value;
 798                 if (v == null) {                // n is deleted
 799                     n.helpDelete(b, f);
 800                     break;
 801                 }
 802                 if (v == n || b.value == null)  // b is deleted
 803                     break;
 804                 int c = key.compareTo(n.key);
 805                 if (c == 0)
 806                     return n;
 807                 if (c < 0)
 808                     return null;
 809                 b = n;
 810                 n = f;
 811             }
 812         }
 813     }
 814 
 815     /**
 816      * Gets value for key using findNode.
 817      * @param okey the key
 818      * @return the value, or null if absent
 819      */
 820     private V doGet(Object okey) {
 821         Comparable<? super K> key = comparable(okey);
 822         /*
 823          * Loop needed here and elsewhere in case value field goes
 824          * null just as it is about to be returned, in which case we
 825          * lost a race with a deletion, so must retry.
 826          */
 827         for (;;) {
 828             Node<K,V> n = findNode(key);
 829             if (n == null)
 830                 return null;
 831             Object v = n.value;
 832             if (v != null)
 833                 return (V)v;
 834         }
 835     }
 836 
 837     /* ---------------- Insertion -------------- */
 838 
 839     /**
 840      * Main insertion method.  Adds element if not present, or
 841      * replaces value if present and onlyIfAbsent is false.
 842      * @param kkey the key
 843      * @param value  the value that must be associated with key
 844      * @param onlyIfAbsent if should not insert if already present
 845      * @return the old value, or null if newly inserted
 846      */
 847     private V doPut(K kkey, V value, boolean onlyIfAbsent) {
 848         Comparable<? super K> key = comparable(kkey);
 849         for (;;) {
 850             Node<K,V> b = findPredecessor(key);
 851             Node<K,V> n = b.next;
 852             for (;;) {
 853                 if (n != null) {
 854                     Node<K,V> f = n.next;
 855                     if (n != b.next)               // inconsistent read
 856                         break;
 857                     Object v = n.value;
 858                     if (v == null) {               // n is deleted
 859                         n.helpDelete(b, f);
 860                         break;
 861                     }
 862                     if (v == n || b.value == null) // b is deleted
 863                         break;
 864                     int c = key.compareTo(n.key);
 865                     if (c > 0) {
 866                         b = n;
 867                         n = f;
 868                         continue;
 869                     }
 870                     if (c == 0) {
 871                         if (onlyIfAbsent || n.casValue(v, value))
 872                             return (V)v;
 873                         else
 874                             break; // restart if lost race to replace value
 875                     }
 876                     // else c < 0; fall through
 877                 }
 878 
 879                 Node<K,V> z = new Node<K,V>(kkey, value, n);
 880                 if (!b.casNext(n, z))
 881                     break;         // restart if lost race to append to b
 882                 int level = randomLevel();
 883                 if (level > 0)
 884                     insertIndex(z, level);
 885                 return null;
 886             }
 887         }
 888     }
 889 
 890     /**
 891      * Returns a random level for inserting a new node.
 892      * Hardwired to k=1, p=0.5, max 31 (see above and
 893      * Pugh's "Skip List Cookbook", sec 3.4).
 894      *
 895      * This uses the simplest of the generators described in George
 896      * Marsaglia's "Xorshift RNGs" paper.  This is not a high-quality
 897      * generator but is acceptable here.
 898      */
 899     private int randomLevel() {
 900         int x = randomSeed;
 901         x ^= x << 13;
 902         x ^= x >>> 17;
 903         randomSeed = x ^= x << 5;
 904         if ((x & 0x80000001) != 0) // test highest and lowest bits
 905             return 0;
 906         int level = 1;
 907         while (((x >>>= 1) & 1) != 0) ++level;
 908         return level;
 909     }
 910 
 911     /**
 912      * Creates and adds index nodes for the given node.
 913      * @param z the node
 914      * @param level the level of the index
 915      */
 916     private void insertIndex(Node<K,V> z, int level) {
 917         HeadIndex<K,V> h = head;
 918         int max = h.level;
 919 
 920         if (level <= max) {
 921             Index<K,V> idx = null;
 922             for (int i = 1; i <= level; ++i)
 923                 idx = new Index<K,V>(z, idx, null);
 924             addIndex(idx, h, level);
 925 
 926         } else { // Add a new level
 927             /*
 928              * To reduce interference by other threads checking for
 929              * empty levels in tryReduceLevel, new levels are added
 930              * with initialized right pointers. Which in turn requires
 931              * keeping levels in an array to access them while
 932              * creating new head index nodes from the opposite
 933              * direction.
 934              */
 935             level = max + 1;
 936             Index<K,V>[] idxs = (Index<K,V>[])new Index<?,?>[level+1];
 937             Index<K,V> idx = null;
 938             for (int i = 1; i <= level; ++i)
 939                 idxs[i] = idx = new Index<K,V>(z, idx, null);
 940 
 941             HeadIndex<K,V> oldh;
 942             int k;
 943             for (;;) {
 944                 oldh = head;
 945                 int oldLevel = oldh.level;
 946                 if (level <= oldLevel) { // lost race to add level
 947                     k = level;
 948                     break;
 949                 }
 950                 HeadIndex<K,V> newh = oldh;
 951                 Node<K,V> oldbase = oldh.node;
 952                 for (int j = oldLevel+1; j <= level; ++j)
 953                     newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);
 954                 if (casHead(oldh, newh)) {
 955                     k = oldLevel;
 956                     break;
 957                 }
 958             }
 959             addIndex(idxs[k], oldh, k);
 960         }
 961     }
 962 
 963     /**
 964      * Adds given index nodes from given level down to 1.
 965      * @param idx the topmost index node being inserted
 966      * @param h the value of head to use to insert. This must be
 967      * snapshotted by callers to provide correct insertion level
 968      * @param indexLevel the level of the index
 969      */
 970     private void addIndex(Index<K,V> idx, HeadIndex<K,V> h, int indexLevel) {
 971         // Track next level to insert in case of retries
 972         int insertionLevel = indexLevel;
 973         Comparable<? super K> key = comparable(idx.node.key);
 974         if (key == null) throw new NullPointerException();
 975 
 976         // Similar to findPredecessor, but adding index nodes along
 977         // path to key.
 978         for (;;) {
 979             int j = h.level;
 980             Index<K,V> q = h;
 981             Index<K,V> r = q.right;
 982             Index<K,V> t = idx;
 983             for (;;) {
 984                 if (r != null) {
 985                     Node<K,V> n = r.node;
 986                     // compare before deletion check avoids needing recheck
 987                     int c = key.compareTo(n.key);
 988                     if (n.value == null) {
 989                         if (!q.unlink(r))
 990                             break;
 991                         r = q.right;
 992                         continue;
 993                     }
 994                     if (c > 0) {
 995                         q = r;
 996                         r = r.right;
 997                         continue;
 998                     }
 999                 }
1000 
1001                 if (j == insertionLevel) {
1002                     // Don't insert index if node already deleted
1003                     if (t.indexesDeletedNode()) {
1004                         findNode(key); // cleans up
1005                         return;
1006                     }
1007                     if (!q.link(r, t))
1008                         break; // restart
1009                     if (--insertionLevel == 0) {
1010                         // need final deletion check before return
1011                         if (t.indexesDeletedNode())
1012                             findNode(key);
1013                         return;
1014                     }
1015                 }
1016 
1017                 if (--j >= insertionLevel && j < indexLevel)
1018                     t = t.down;
1019                 q = q.down;
1020                 r = q.right;
1021             }
1022         }
1023     }
1024 
1025     /* ---------------- Deletion -------------- */
1026 
1027     /**
1028      * Main deletion method. Locates node, nulls value, appends a
1029      * deletion marker, unlinks predecessor, removes associated index
1030      * nodes, and possibly reduces head index level.
1031      *
1032      * Index nodes are cleared out simply by calling findPredecessor.
1033      * which unlinks indexes to deleted nodes found along path to key,
1034      * which will include the indexes to this node.  This is done
1035      * unconditionally. We can't check beforehand whether there are
1036      * index nodes because it might be the case that some or all
1037      * indexes hadn't been inserted yet for this node during initial
1038      * search for it, and we'd like to ensure lack of garbage
1039      * retention, so must call to be sure.
1040      *
1041      * @param okey the key
1042      * @param value if non-null, the value that must be
1043      * associated with key
1044      * @return the node, or null if not found
1045      */
1046     final V doRemove(Object okey, Object value) {
1047         Comparable<? super K> key = comparable(okey);
1048         for (;;) {
1049             Node<K,V> b = findPredecessor(key);
1050             Node<K,V> n = b.next;
1051             for (;;) {
1052                 if (n == null)
1053                     return null;
1054                 Node<K,V> f = n.next;
1055                 if (n != b.next)                    // inconsistent read
1056                     break;
1057                 Object v = n.value;
1058                 if (v == null) {                    // n is deleted
1059                     n.helpDelete(b, f);
1060                     break;
1061                 }
1062                 if (v == n || b.value == null)      // b is deleted
1063                     break;
1064                 int c = key.compareTo(n.key);
1065                 if (c < 0)
1066                     return null;
1067                 if (c > 0) {
1068                     b = n;
1069                     n = f;
1070                     continue;
1071                 }
1072                 if (value != null && !value.equals(v))
1073                     return null;
1074                 if (!n.casValue(v, null))
1075                     break;
1076                 if (!n.appendMarker(f) || !b.casNext(n, f))
1077                     findNode(key);                  // Retry via findNode
1078                 else {
1079                     findPredecessor(key);           // Clean index
1080                     if (head.right == null)
1081                         tryReduceLevel();
1082                 }
1083                 return (V)v;
1084             }
1085         }
1086     }
1087 
1088     /**
1089      * Possibly reduce head level if it has no nodes.  This method can
1090      * (rarely) make mistakes, in which case levels can disappear even
1091      * though they are about to contain index nodes. This impacts
1092      * performance, not correctness.  To minimize mistakes as well as
1093      * to reduce hysteresis, the level is reduced by one only if the
1094      * topmost three levels look empty. Also, if the removed level
1095      * looks non-empty after CAS, we try to change it back quick
1096      * before anyone notices our mistake! (This trick works pretty
1097      * well because this method will practically never make mistakes
1098      * unless current thread stalls immediately before first CAS, in
1099      * which case it is very unlikely to stall again immediately
1100      * afterwards, so will recover.)
1101      *
1102      * We put up with all this rather than just let levels grow
1103      * because otherwise, even a small map that has undergone a large
1104      * number of insertions and removals will have a lot of levels,
1105      * slowing down access more than would an occasional unwanted
1106      * reduction.
1107      */
1108     private void tryReduceLevel() {
1109         HeadIndex<K,V> h = head;
1110         HeadIndex<K,V> d;
1111         HeadIndex<K,V> e;
1112         if (h.level > 3 &&
1113             (d = (HeadIndex<K,V>)h.down) != null &&
1114             (e = (HeadIndex<K,V>)d.down) != null &&
1115             e.right == null &&
1116             d.right == null &&
1117             h.right == null &&
1118             casHead(h, d) && // try to set
1119             h.right != null) // recheck
1120             casHead(d, h);   // try to backout
1121     }
1122 
1123     /* ---------------- Finding and removing first element -------------- */
1124 
1125     /**
1126      * Specialized variant of findNode to get first valid node.
1127      * @return first node or null if empty
1128      */
1129     Node<K,V> findFirst() {
1130         for (;;) {
1131             Node<K,V> b = head.node;
1132             Node<K,V> n = b.next;
1133             if (n == null)
1134                 return null;
1135             if (n.value != null)
1136                 return n;
1137             n.helpDelete(b, n.next);
1138         }
1139     }
1140 
1141     /**
1142      * Removes first entry; returns its snapshot.
1143      * @return null if empty, else snapshot of first entry
1144      */
1145     Map.Entry<K,V> doRemoveFirstEntry() {
1146         for (;;) {
1147             Node<K,V> b = head.node;
1148             Node<K,V> n = b.next;
1149             if (n == null)
1150                 return null;
1151             Node<K,V> f = n.next;
1152             if (n != b.next)
1153                 continue;
1154             Object v = n.value;
1155             if (v == null) {
1156                 n.helpDelete(b, f);
1157                 continue;
1158             }
1159             if (!n.casValue(v, null))
1160                 continue;
1161             if (!n.appendMarker(f) || !b.casNext(n, f))
1162                 findFirst(); // retry
1163             clearIndexToFirst();
1164             return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, (V)v);
1165         }
1166     }
1167 
1168     /**
1169      * Clears out index nodes associated with deleted first entry.
1170      */
1171     private void clearIndexToFirst() {
1172         for (;;) {
1173             Index<K,V> q = head;
1174             for (;;) {
1175                 Index<K,V> r = q.right;
1176                 if (r != null && r.indexesDeletedNode() && !q.unlink(r))
1177                     break;
1178                 if ((q = q.down) == null) {
1179                     if (head.right == null)
1180                         tryReduceLevel();
1181                     return;
1182                 }
1183             }
1184         }
1185     }
1186 
1187 
1188     /* ---------------- Finding and removing last element -------------- */
1189 
1190     /**
1191      * Specialized version of find to get last valid node.
1192      * @return last node or null if empty
1193      */
1194     Node<K,V> findLast() {
1195         /*
1196          * findPredecessor can't be used to traverse index level
1197          * because this doesn't use comparisons.  So traversals of
1198          * both levels are folded together.
1199          */
1200         Index<K,V> q = head;
1201         for (;;) {
1202             Index<K,V> d, r;
1203             if ((r = q.right) != null) {
1204                 if (r.indexesDeletedNode()) {
1205                     q.unlink(r);
1206                     q = head; // restart
1207                 }
1208                 else
1209                     q = r;
1210             } else if ((d = q.down) != null) {
1211                 q = d;
1212             } else {
1213                 Node<K,V> b = q.node;
1214                 Node<K,V> n = b.next;
1215                 for (;;) {
1216                     if (n == null)
1217                         return b.isBaseHeader() ? null : b;
1218                     Node<K,V> f = n.next;            // inconsistent read
1219                     if (n != b.next)
1220                         break;
1221                     Object v = n.value;
1222                     if (v == null) {                 // n is deleted
1223                         n.helpDelete(b, f);
1224                         break;
1225                     }
1226                     if (v == n || b.value == null)   // b is deleted
1227                         break;
1228                     b = n;
1229                     n = f;
1230                 }
1231                 q = head; // restart
1232             }
1233         }
1234     }
1235 
1236     /**
1237      * Specialized variant of findPredecessor to get predecessor of last
1238      * valid node.  Needed when removing the last entry.  It is possible
1239      * that all successors of returned node will have been deleted upon
1240      * return, in which case this method can be retried.
1241      * @return likely predecessor of last node
1242      */
1243     private Node<K,V> findPredecessorOfLast() {
1244         for (;;) {
1245             Index<K,V> q = head;
1246             for (;;) {
1247                 Index<K,V> d, r;
1248                 if ((r = q.right) != null) {
1249                     if (r.indexesDeletedNode()) {
1250                         q.unlink(r);
1251                         break;    // must restart
1252                     }
1253                     // proceed as far across as possible without overshooting
1254                     if (r.node.next != null) {
1255                         q = r;
1256                         continue;
1257                     }
1258                 }
1259                 if ((d = q.down) != null)
1260                     q = d;
1261                 else
1262                     return q.node;
1263             }
1264         }
1265     }
1266 
1267     /**
1268      * Removes last entry; returns its snapshot.
1269      * Specialized variant of doRemove.
1270      * @return null if empty, else snapshot of last entry
1271      */
1272     Map.Entry<K,V> doRemoveLastEntry() {
1273         for (;;) {
1274             Node<K,V> b = findPredecessorOfLast();
1275             Node<K,V> n = b.next;
1276             if (n == null) {
1277                 if (b.isBaseHeader())               // empty
1278                     return null;
1279                 else
1280                     continue; // all b's successors are deleted; retry
1281             }
1282             for (;;) {
1283                 Node<K,V> f = n.next;
1284                 if (n != b.next)                    // inconsistent read
1285                     break;
1286                 Object v = n.value;
1287                 if (v == null) {                    // n is deleted
1288                     n.helpDelete(b, f);
1289                     break;
1290                 }
1291                 if (v == n || b.value == null)      // b is deleted
1292                     break;
1293                 if (f != null) {
1294                     b = n;
1295                     n = f;
1296                     continue;
1297                 }
1298                 if (!n.casValue(v, null))
1299                     break;
1300                 K key = n.key;
1301                 Comparable<? super K> ck = comparable(key);
1302                 if (!n.appendMarker(f) || !b.casNext(n, f))
1303                     findNode(ck);                  // Retry via findNode
1304                 else {
1305                     findPredecessor(ck);           // Clean index
1306                     if (head.right == null)
1307                         tryReduceLevel();
1308                 }
1309                 return new AbstractMap.SimpleImmutableEntry<K,V>(key, (V)v);
1310             }
1311         }
1312     }
1313 
1314     /* ---------------- Relational operations -------------- */
1315 
1316     // Control values OR'ed as arguments to findNear
1317 
1318     private static final int EQ = 1;
1319     private static final int LT = 2;
1320     private static final int GT = 0; // Actually checked as !LT
1321 
1322     /**
1323      * Utility for ceiling, floor, lower, higher methods.
1324      * @param kkey the key
1325      * @param rel the relation -- OR'ed combination of EQ, LT, GT
1326      * @return nearest node fitting relation, or null if no such
1327      */
1328     Node<K,V> findNear(K kkey, int rel) {
1329         Comparable<? super K> key = comparable(kkey);
1330         for (;;) {
1331             Node<K,V> b = findPredecessor(key);
1332             Node<K,V> n = b.next;
1333             for (;;) {
1334                 if (n == null)
1335                     return ((rel & LT) == 0 || b.isBaseHeader()) ? null : b;
1336                 Node<K,V> f = n.next;
1337                 if (n != b.next)                  // inconsistent read
1338                     break;
1339                 Object v = n.value;
1340                 if (v == null) {                  // n is deleted
1341                     n.helpDelete(b, f);
1342                     break;
1343                 }
1344                 if (v == n || b.value == null)    // b is deleted
1345                     break;
1346                 int c = key.compareTo(n.key);
1347                 if ((c == 0 && (rel & EQ) != 0) ||
1348                     (c <  0 && (rel & LT) == 0))
1349                     return n;
1350                 if ( c <= 0 && (rel & LT) != 0)
1351                     return b.isBaseHeader() ? null : b;
1352                 b = n;
1353                 n = f;
1354             }
1355         }
1356     }
1357 
1358     /**
1359      * Returns SimpleImmutableEntry for results of findNear.
1360      * @param key the key
1361      * @param rel the relation -- OR'ed combination of EQ, LT, GT
1362      * @return Entry fitting relation, or null if no such
1363      */
1364     AbstractMap.SimpleImmutableEntry<K,V> getNear(K key, int rel) {
1365         for (;;) {
1366             Node<K,V> n = findNear(key, rel);
1367             if (n == null)
1368                 return null;
1369             AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
1370             if (e != null)
1371                 return e;
1372         }
1373     }
1374 
1375 
1376     /* ---------------- Constructors -------------- */
1377 
1378     /**
1379      * Constructs a new, empty map, sorted according to the
1380      * {@linkplain Comparable natural ordering} of the keys.
1381      */
1382     public ConcurrentSkipListMap() {
1383         this.comparator = null;
1384         initialize();
1385     }
1386 
1387     /**
1388      * Constructs a new, empty map, sorted according to the specified
1389      * comparator.
1390      *
1391      * @param comparator the comparator that will be used to order this map.
1392      *        If <tt>null</tt>, the {@linkplain Comparable natural
1393      *        ordering} of the keys will be used.
1394      */
1395     public ConcurrentSkipListMap(Comparator<? super K> comparator) {
1396         this.comparator = comparator;
1397         initialize();
1398     }
1399 
1400     /**
1401      * Constructs a new map containing the same mappings as the given map,
1402      * sorted according to the {@linkplain Comparable natural ordering} of
1403      * the keys.
1404      *
1405      * @param  m the map whose mappings are to be placed in this map
1406      * @throws ClassCastException if the keys in <tt>m</tt> are not
1407      *         {@link Comparable}, or are not mutually comparable
1408      * @throws NullPointerException if the specified map or any of its keys
1409      *         or values are null
1410      */
1411     public ConcurrentSkipListMap(Map<? extends K, ? extends V> m) {
1412         this.comparator = null;
1413         initialize();
1414         putAll(m);
1415     }
1416 
1417     /**
1418      * Constructs a new map containing the same mappings and using the
1419      * same ordering as the specified sorted map.
1420      *
1421      * @param m the sorted map whose mappings are to be placed in this
1422      *        map, and whose comparator is to be used to sort this map
1423      * @throws NullPointerException if the specified sorted map or any of
1424      *         its keys or values are null
1425      */
1426     public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) {
1427         this.comparator = m.comparator();
1428         initialize();
1429         buildFromSorted(m);
1430     }
1431 
1432     /**
1433      * Returns a shallow copy of this <tt>ConcurrentSkipListMap</tt>
1434      * instance. (The keys and values themselves are not cloned.)
1435      *
1436      * @return a shallow copy of this map
1437      */
1438     public ConcurrentSkipListMap<K,V> clone() {

1439         try {
1440             @SuppressWarnings("unchecked")
1441             ConcurrentSkipListMap<K,V> clone =
1442                 (ConcurrentSkipListMap<K,V>) super.clone();


1443             clone.initialize();
1444             clone.buildFromSorted(this);
1445             return clone;
1446         } catch (CloneNotSupportedException e) {
1447             throw new InternalError();
1448         }
1449     }
1450 
1451     /**
1452      * Streamlined bulk insertion to initialize from elements of
1453      * given sorted map.  Call only from constructor or clone
1454      * method.
1455      */
1456     private void buildFromSorted(SortedMap<K, ? extends V> map) {
1457         if (map == null)
1458             throw new NullPointerException();
1459 
1460         HeadIndex<K,V> h = head;
1461         Node<K,V> basepred = h.node;
1462 
1463         // Track the current rightmost node at each level. Uses an
1464         // ArrayList to avoid committing to initial or maximum level.
1465         ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>();
1466 
1467         // initialize
1468         for (int i = 0; i <= h.level; ++i)
1469             preds.add(null);
1470         Index<K,V> q = h;
1471         for (int i = h.level; i > 0; --i) {
1472             preds.set(i, q);
1473             q = q.down;
1474         }
1475 
1476         Iterator<? extends Map.Entry<? extends K, ? extends V>> it =
1477             map.entrySet().iterator();
1478         while (it.hasNext()) {
1479             Map.Entry<? extends K, ? extends V> e = it.next();
1480             int j = randomLevel();
1481             if (j > h.level) j = h.level + 1;
1482             K k = e.getKey();
1483             V v = e.getValue();
1484             if (k == null || v == null)
1485                 throw new NullPointerException();
1486             Node<K,V> z = new Node<K,V>(k, v, null);
1487             basepred.next = z;
1488             basepred = z;
1489             if (j > 0) {
1490                 Index<K,V> idx = null;
1491                 for (int i = 1; i <= j; ++i) {
1492                     idx = new Index<K,V>(z, idx, null);
1493                     if (i > h.level)
1494                         h = new HeadIndex<K,V>(h.node, h, idx, i);
1495 
1496                     if (i < preds.size()) {
1497                         preds.get(i).right = idx;
1498                         preds.set(i, idx);
1499                     } else
1500                         preds.add(idx);
1501                 }
1502             }
1503         }
1504         head = h;
1505     }
1506 
1507     /* ---------------- Serialization -------------- */
1508 
1509     /**
1510      * Saves the state of this map to a stream (that is, serializes it).
1511      *
1512      * @serialData The key (Object) and value (Object) for each
1513      * key-value mapping represented by the map, followed by
1514      * <tt>null</tt>. The key-value mappings are emitted in key-order
1515      * (as determined by the Comparator, or by the keys' natural
1516      * ordering if no Comparator).
1517      */
1518     private void writeObject(java.io.ObjectOutputStream s)
1519         throws java.io.IOException {
1520         // Write out the Comparator and any hidden stuff
1521         s.defaultWriteObject();
1522 
1523         // Write out keys and values (alternating)
1524         for (Node<K,V> n = findFirst(); n != null; n = n.next) {
1525             V v = n.getValidValue();
1526             if (v != null) {
1527                 s.writeObject(n.key);
1528                 s.writeObject(v);
1529             }
1530         }
1531         s.writeObject(null);
1532     }
1533 
1534     /**
1535      * Reconstitutes the map from a stream (that is, deserializes it).
1536      *
1537      * @param s the stream
1538      */
1539     private void readObject(final java.io.ObjectInputStream s)
1540         throws java.io.IOException, ClassNotFoundException {
1541         // Read in the Comparator and any hidden stuff
1542         s.defaultReadObject();
1543         // Reset transients
1544         initialize();
1545 
1546         /*
1547          * This is nearly identical to buildFromSorted, but is
1548          * distinct because readObject calls can't be nicely adapted
1549          * as the kind of iterator needed by buildFromSorted. (They
1550          * can be, but doing so requires type cheats and/or creation
1551          * of adaptor classes.) It is simpler to just adapt the code.
1552          */
1553 
1554         HeadIndex<K,V> h = head;
1555         Node<K,V> basepred = h.node;
1556         ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>();
1557         for (int i = 0; i <= h.level; ++i)
1558             preds.add(null);
1559         Index<K,V> q = h;
1560         for (int i = h.level; i > 0; --i) {
1561             preds.set(i, q);
1562             q = q.down;
1563         }
1564 
1565         for (;;) {
1566             Object k = s.readObject();
1567             if (k == null)
1568                 break;
1569             Object v = s.readObject();
1570             if (v == null)
1571                 throw new NullPointerException();
1572             K key = (K) k;
1573             V val = (V) v;
1574             int j = randomLevel();
1575             if (j > h.level) j = h.level + 1;
1576             Node<K,V> z = new Node<K,V>(key, val, null);
1577             basepred.next = z;
1578             basepred = z;
1579             if (j > 0) {
1580                 Index<K,V> idx = null;
1581                 for (int i = 1; i <= j; ++i) {
1582                     idx = new Index<K,V>(z, idx, null);
1583                     if (i > h.level)
1584                         h = new HeadIndex<K,V>(h.node, h, idx, i);
1585 
1586                     if (i < preds.size()) {
1587                         preds.get(i).right = idx;
1588                         preds.set(i, idx);
1589                     } else
1590                         preds.add(idx);
1591                 }
1592             }
1593         }
1594         head = h;
1595     }
1596 
1597     /* ------ Map API methods ------ */
1598 
1599     /**
1600      * Returns <tt>true</tt> if this map contains a mapping for the specified
1601      * key.
1602      *
1603      * @param key key whose presence in this map is to be tested
1604      * @return <tt>true</tt> if this map contains a mapping for the specified key
1605      * @throws ClassCastException if the specified key cannot be compared
1606      *         with the keys currently in the map
1607      * @throws NullPointerException if the specified key is null
1608      */
1609     public boolean containsKey(Object key) {
1610         return doGet(key) != null;
1611     }
1612 
1613     /**
1614      * Returns the value to which the specified key is mapped,
1615      * or {@code null} if this map contains no mapping for the key.
1616      *
1617      * <p>More formally, if this map contains a mapping from a key
1618      * {@code k} to a value {@code v} such that {@code key} compares
1619      * equal to {@code k} according to the map's ordering, then this
1620      * method returns {@code v}; otherwise it returns {@code null}.
1621      * (There can be at most one such mapping.)
1622      *
1623      * @throws ClassCastException if the specified key cannot be compared
1624      *         with the keys currently in the map
1625      * @throws NullPointerException if the specified key is null
1626      */
1627     public V get(Object key) {
1628         return doGet(key);
1629     }
1630 
1631     /**
1632      * Associates the specified value with the specified key in this map.
1633      * If the map previously contained a mapping for the key, the old
1634      * value is replaced.
1635      *
1636      * @param key key with which the specified value is to be associated
1637      * @param value value to be associated with the specified key
1638      * @return the previous value associated with the specified key, or
1639      *         <tt>null</tt> if there was no mapping for the key
1640      * @throws ClassCastException if the specified key cannot be compared
1641      *         with the keys currently in the map
1642      * @throws NullPointerException if the specified key or value is null
1643      */
1644     public V put(K key, V value) {
1645         if (value == null)
1646             throw new NullPointerException();
1647         return doPut(key, value, false);
1648     }
1649 
1650     /**
1651      * Removes the mapping for the specified key from this map if present.
1652      *
1653      * @param  key key for which mapping should be removed
1654      * @return the previous value associated with the specified key, or
1655      *         <tt>null</tt> if there was no mapping for the key
1656      * @throws ClassCastException if the specified key cannot be compared
1657      *         with the keys currently in the map
1658      * @throws NullPointerException if the specified key is null
1659      */
1660     public V remove(Object key) {
1661         return doRemove(key, null);
1662     }
1663 
1664     /**
1665      * Returns <tt>true</tt> if this map maps one or more keys to the
1666      * specified value.  This operation requires time linear in the
1667      * map size. Additionally, it is possible for the map to change
1668      * during execution of this method, in which case the returned
1669      * result may be inaccurate.
1670      *
1671      * @param value value whose presence in this map is to be tested
1672      * @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
1673      *         <tt>false</tt> otherwise
1674      * @throws NullPointerException if the specified value is null
1675      */
1676     public boolean containsValue(Object value) {
1677         if (value == null)
1678             throw new NullPointerException();
1679         for (Node<K,V> n = findFirst(); n != null; n = n.next) {
1680             V v = n.getValidValue();
1681             if (v != null && value.equals(v))
1682                 return true;
1683         }
1684         return false;
1685     }
1686 
1687     /**
1688      * Returns the number of key-value mappings in this map.  If this map
1689      * contains more than <tt>Integer.MAX_VALUE</tt> elements, it
1690      * returns <tt>Integer.MAX_VALUE</tt>.
1691      *
1692      * <p>Beware that, unlike in most collections, this method is
1693      * <em>NOT</em> a constant-time operation. Because of the
1694      * asynchronous nature of these maps, determining the current
1695      * number of elements requires traversing them all to count them.
1696      * Additionally, it is possible for the size to change during
1697      * execution of this method, in which case the returned result
1698      * will be inaccurate. Thus, this method is typically not very
1699      * useful in concurrent applications.
1700      *
1701      * @return the number of elements in this map
1702      */
1703     public int size() {
1704         long count = 0;
1705         for (Node<K,V> n = findFirst(); n != null; n = n.next) {
1706             if (n.getValidValue() != null)
1707                 ++count;
1708         }
1709         return (count >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int) count;
1710     }
1711 
1712     /**
1713      * Returns <tt>true</tt> if this map contains no key-value mappings.
1714      * @return <tt>true</tt> if this map contains no key-value mappings
1715      */
1716     public boolean isEmpty() {
1717         return findFirst() == null;
1718     }
1719 
1720     /**
1721      * Removes all of the mappings from this map.
1722      */
1723     public void clear() {
1724         initialize();
1725     }
1726 
1727     /* ---------------- View methods -------------- */
1728 
1729     /*
1730      * Note: Lazy initialization works for views because view classes
1731      * are stateless/immutable so it doesn't matter wrt correctness if
1732      * more than one is created (which will only rarely happen).  Even
1733      * so, the following idiom conservatively ensures that the method
1734      * returns the one it created if it does so, not one created by
1735      * another racing thread.
1736      */
1737 
1738     /**
1739      * Returns a {@link NavigableSet} view of the keys contained in this map.
1740      * The set's iterator returns the keys in ascending order.
1741      * The set is backed by the map, so changes to the map are
1742      * reflected in the set, and vice-versa.  The set supports element
1743      * removal, which removes the corresponding mapping from the map,
1744      * via the {@code Iterator.remove}, {@code Set.remove},
1745      * {@code removeAll}, {@code retainAll}, and {@code clear}
1746      * operations.  It does not support the {@code add} or {@code addAll}
1747      * operations.
1748      *
1749      * <p>The view's {@code iterator} is a "weakly consistent" iterator
1750      * that will never throw {@link ConcurrentModificationException},
1751      * and guarantees to traverse elements as they existed upon
1752      * construction of the iterator, and may (but is not guaranteed to)
1753      * reflect any modifications subsequent to construction.
1754      *
1755      * <p>This method is equivalent to method {@code navigableKeySet}.
1756      *
1757      * @return a navigable set view of the keys in this map
1758      */
1759     public NavigableSet<K> keySet() {
1760         KeySet<K> ks = keySet;
1761         return (ks != null) ? ks : (keySet = new KeySet<K>(this));
1762     }
1763 
1764     public NavigableSet<K> navigableKeySet() {
1765         KeySet<K> ks = keySet;
1766         return (ks != null) ? ks : (keySet = new KeySet<K>(this));
1767     }
1768 
1769     /**
1770      * Returns a {@link Collection} view of the values contained in this map.
1771      * The collection's iterator returns the values in ascending order
1772      * of the corresponding keys.
1773      * The collection is backed by the map, so changes to the map are
1774      * reflected in the collection, and vice-versa.  The collection
1775      * supports element removal, which removes the corresponding
1776      * mapping from the map, via the <tt>Iterator.remove</tt>,
1777      * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1778      * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
1779      * support the <tt>add</tt> or <tt>addAll</tt> operations.
1780      *
1781      * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1782      * that will never throw {@link ConcurrentModificationException},
1783      * and guarantees to traverse elements as they existed upon
1784      * construction of the iterator, and may (but is not guaranteed to)
1785      * reflect any modifications subsequent to construction.
1786      */
1787     public Collection<V> values() {
1788         Values<V> vs = values;
1789         return (vs != null) ? vs : (values = new Values<V>(this));
1790     }
1791 
1792     /**
1793      * Returns a {@link Set} view of the mappings contained in this map.
1794      * The set's iterator returns the entries in ascending key order.
1795      * The set is backed by the map, so changes to the map are
1796      * reflected in the set, and vice-versa.  The set supports element
1797      * removal, which removes the corresponding mapping from the map,
1798      * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1799      * <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
1800      * operations.  It does not support the <tt>add</tt> or
1801      * <tt>addAll</tt> operations.
1802      *
1803      * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1804      * that will never throw {@link ConcurrentModificationException},
1805      * and guarantees to traverse elements as they existed upon
1806      * construction of the iterator, and may (but is not guaranteed to)
1807      * reflect any modifications subsequent to construction.
1808      *
1809      * <p>The <tt>Map.Entry</tt> elements returned by
1810      * <tt>iterator.next()</tt> do <em>not</em> support the
1811      * <tt>setValue</tt> operation.
1812      *
1813      * @return a set view of the mappings contained in this map,
1814      *         sorted in ascending key order
1815      */
1816     public Set<Map.Entry<K,V>> entrySet() {
1817         EntrySet<K,V> es = entrySet;
1818         return (es != null) ? es : (entrySet = new EntrySet<K,V>(this));
1819     }
1820 
1821     public ConcurrentNavigableMap<K,V> descendingMap() {
1822         ConcurrentNavigableMap<K,V> dm = descendingMap;
1823         return (dm != null) ? dm : (descendingMap = new SubMap<K,V>
1824                                     (this, null, false, null, false, true));
1825     }
1826 
1827     public NavigableSet<K> descendingKeySet() {
1828         return descendingMap().navigableKeySet();
1829     }
1830 
1831     /* ---------------- AbstractMap Overrides -------------- */
1832 
1833     /**
1834      * Compares the specified object with this map for equality.
1835      * Returns <tt>true</tt> if the given object is also a map and the
1836      * two maps represent the same mappings.  More formally, two maps
1837      * <tt>m1</tt> and <tt>m2</tt> represent the same mappings if
1838      * <tt>m1.entrySet().equals(m2.entrySet())</tt>.  This
1839      * operation may return misleading results if either map is
1840      * concurrently modified during execution of this method.
1841      *
1842      * @param o object to be compared for equality with this map
1843      * @return <tt>true</tt> if the specified object is equal to this map
1844      */
1845     public boolean equals(Object o) {
1846         if (o == this)
1847             return true;
1848         if (!(o instanceof Map))
1849             return false;
1850         Map<?,?> m = (Map<?,?>) o;
1851         try {
1852             for (Map.Entry<K,V> e : this.entrySet())
1853                 if (! e.getValue().equals(m.get(e.getKey())))
1854                     return false;
1855             for (Map.Entry<?,?> e : m.entrySet()) {
1856                 Object k = e.getKey();
1857                 Object v = e.getValue();
1858                 if (k == null || v == null || !v.equals(get(k)))
1859                     return false;
1860             }
1861             return true;
1862         } catch (ClassCastException unused) {
1863             return false;
1864         } catch (NullPointerException unused) {
1865             return false;
1866         }
1867     }
1868 
1869     /* ------ ConcurrentMap API methods ------ */
1870 
1871     /**
1872      * {@inheritDoc}
1873      *
1874      * @return the previous value associated with the specified key,
1875      *         or <tt>null</tt> if there was no mapping for the key
1876      * @throws ClassCastException if the specified key cannot be compared
1877      *         with the keys currently in the map
1878      * @throws NullPointerException if the specified key or value is null
1879      */
1880     public V putIfAbsent(K key, V value) {
1881         if (value == null)
1882             throw new NullPointerException();
1883         return doPut(key, value, true);
1884     }
1885 
1886     /**
1887      * {@inheritDoc}
1888      *
1889      * @throws ClassCastException if the specified key cannot be compared
1890      *         with the keys currently in the map
1891      * @throws NullPointerException if the specified key is null
1892      */
1893     public boolean remove(Object key, Object value) {
1894         if (key == null)
1895             throw new NullPointerException();
1896         if (value == null)
1897             return false;
1898         return doRemove(key, value) != null;
1899     }
1900 
1901     /**
1902      * {@inheritDoc}
1903      *
1904      * @throws ClassCastException if the specified key cannot be compared
1905      *         with the keys currently in the map
1906      * @throws NullPointerException if any of the arguments are null
1907      */
1908     public boolean replace(K key, V oldValue, V newValue) {
1909         if (oldValue == null || newValue == null)
1910             throw new NullPointerException();
1911         Comparable<? super K> k = comparable(key);
1912         for (;;) {
1913             Node<K,V> n = findNode(k);
1914             if (n == null)
1915                 return false;
1916             Object v = n.value;
1917             if (v != null) {
1918                 if (!oldValue.equals(v))
1919                     return false;
1920                 if (n.casValue(v, newValue))
1921                     return true;
1922             }
1923         }
1924     }
1925 
1926     /**
1927      * {@inheritDoc}
1928      *
1929      * @return the previous value associated with the specified key,
1930      *         or <tt>null</tt> if there was no mapping for the key
1931      * @throws ClassCastException if the specified key cannot be compared
1932      *         with the keys currently in the map
1933      * @throws NullPointerException if the specified key or value is null
1934      */
1935     public V replace(K key, V value) {
1936         if (value == null)
1937             throw new NullPointerException();
1938         Comparable<? super K> k = comparable(key);
1939         for (;;) {
1940             Node<K,V> n = findNode(k);
1941             if (n == null)
1942                 return null;
1943             Object v = n.value;
1944             if (v != null && n.casValue(v, value))
1945                 return (V)v;
1946         }
1947     }
1948 
1949     /* ------ SortedMap API methods ------ */
1950 
1951     public Comparator<? super K> comparator() {
1952         return comparator;
1953     }
1954 
1955     /**
1956      * @throws NoSuchElementException {@inheritDoc}
1957      */
1958     public K firstKey() {
1959         Node<K,V> n = findFirst();
1960         if (n == null)
1961             throw new NoSuchElementException();
1962         return n.key;
1963     }
1964 
1965     /**
1966      * @throws NoSuchElementException {@inheritDoc}
1967      */
1968     public K lastKey() {
1969         Node<K,V> n = findLast();
1970         if (n == null)
1971             throw new NoSuchElementException();
1972         return n.key;
1973     }
1974 
1975     /**
1976      * @throws ClassCastException {@inheritDoc}
1977      * @throws NullPointerException if {@code fromKey} or {@code toKey} is null
1978      * @throws IllegalArgumentException {@inheritDoc}
1979      */
1980     public ConcurrentNavigableMap<K,V> subMap(K fromKey,
1981                                               boolean fromInclusive,
1982                                               K toKey,
1983                                               boolean toInclusive) {
1984         if (fromKey == null || toKey == null)
1985             throw new NullPointerException();
1986         return new SubMap<K,V>
1987             (this, fromKey, fromInclusive, toKey, toInclusive, false);
1988     }
1989 
1990     /**
1991      * @throws ClassCastException {@inheritDoc}
1992      * @throws NullPointerException if {@code toKey} is null
1993      * @throws IllegalArgumentException {@inheritDoc}
1994      */
1995     public ConcurrentNavigableMap<K,V> headMap(K toKey,
1996                                                boolean inclusive) {
1997         if (toKey == null)
1998             throw new NullPointerException();
1999         return new SubMap<K,V>
2000             (this, null, false, toKey, inclusive, false);
2001     }
2002 
2003     /**
2004      * @throws ClassCastException {@inheritDoc}
2005      * @throws NullPointerException if {@code fromKey} is null
2006      * @throws IllegalArgumentException {@inheritDoc}
2007      */
2008     public ConcurrentNavigableMap<K,V> tailMap(K fromKey,
2009                                                boolean inclusive) {
2010         if (fromKey == null)
2011             throw new NullPointerException();
2012         return new SubMap<K,V>
2013             (this, fromKey, inclusive, null, false, false);
2014     }
2015 
2016     /**
2017      * @throws ClassCastException {@inheritDoc}
2018      * @throws NullPointerException if {@code fromKey} or {@code toKey} is null
2019      * @throws IllegalArgumentException {@inheritDoc}
2020      */
2021     public ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey) {
2022         return subMap(fromKey, true, toKey, false);
2023     }
2024 
2025     /**
2026      * @throws ClassCastException {@inheritDoc}
2027      * @throws NullPointerException if {@code toKey} is null
2028      * @throws IllegalArgumentException {@inheritDoc}
2029      */
2030     public ConcurrentNavigableMap<K,V> headMap(K toKey) {
2031         return headMap(toKey, false);
2032     }
2033 
2034     /**
2035      * @throws ClassCastException {@inheritDoc}
2036      * @throws NullPointerException if {@code fromKey} is null
2037      * @throws IllegalArgumentException {@inheritDoc}
2038      */
2039     public ConcurrentNavigableMap<K,V> tailMap(K fromKey) {
2040         return tailMap(fromKey, true);
2041     }
2042 
2043     /* ---------------- Relational operations -------------- */
2044 
2045     /**
2046      * Returns a key-value mapping associated with the greatest key
2047      * strictly less than the given key, or <tt>null</tt> if there is
2048      * no such key. The returned entry does <em>not</em> support the
2049      * <tt>Entry.setValue</tt> method.
2050      *
2051      * @throws ClassCastException {@inheritDoc}
2052      * @throws NullPointerException if the specified key is null
2053      */
2054     public Map.Entry<K,V> lowerEntry(K key) {
2055         return getNear(key, LT);
2056     }
2057 
2058     /**
2059      * @throws ClassCastException {@inheritDoc}
2060      * @throws NullPointerException if the specified key is null
2061      */
2062     public K lowerKey(K key) {
2063         Node<K,V> n = findNear(key, LT);
2064         return (n == null) ? null : n.key;
2065     }
2066 
2067     /**
2068      * Returns a key-value mapping associated with the greatest key
2069      * less than or equal to the given key, or <tt>null</tt> if there
2070      * is no such key. The returned entry does <em>not</em> support
2071      * the <tt>Entry.setValue</tt> method.
2072      *
2073      * @param key the key
2074      * @throws ClassCastException {@inheritDoc}
2075      * @throws NullPointerException if the specified key is null
2076      */
2077     public Map.Entry<K,V> floorEntry(K key) {
2078         return getNear(key, LT|EQ);
2079     }
2080 
2081     /**
2082      * @param key the key
2083      * @throws ClassCastException {@inheritDoc}
2084      * @throws NullPointerException if the specified key is null
2085      */
2086     public K floorKey(K key) {
2087         Node<K,V> n = findNear(key, LT|EQ);
2088         return (n == null) ? null : n.key;
2089     }
2090 
2091     /**
2092      * Returns a key-value mapping associated with the least key
2093      * greater than or equal to the given key, or <tt>null</tt> if
2094      * there is no such entry. The returned entry does <em>not</em>
2095      * support the <tt>Entry.setValue</tt> method.
2096      *
2097      * @throws ClassCastException {@inheritDoc}
2098      * @throws NullPointerException if the specified key is null
2099      */
2100     public Map.Entry<K,V> ceilingEntry(K key) {
2101         return getNear(key, GT|EQ);
2102     }
2103 
2104     /**
2105      * @throws ClassCastException {@inheritDoc}
2106      * @throws NullPointerException if the specified key is null
2107      */
2108     public K ceilingKey(K key) {
2109         Node<K,V> n = findNear(key, GT|EQ);
2110         return (n == null) ? null : n.key;
2111     }
2112 
2113     /**
2114      * Returns a key-value mapping associated with the least key
2115      * strictly greater than the given key, or <tt>null</tt> if there
2116      * is no such key. The returned entry does <em>not</em> support
2117      * the <tt>Entry.setValue</tt> method.
2118      *
2119      * @param key the key
2120      * @throws ClassCastException {@inheritDoc}
2121      * @throws NullPointerException if the specified key is null
2122      */
2123     public Map.Entry<K,V> higherEntry(K key) {
2124         return getNear(key, GT);
2125     }
2126 
2127     /**
2128      * @param key the key
2129      * @throws ClassCastException {@inheritDoc}
2130      * @throws NullPointerException if the specified key is null
2131      */
2132     public K higherKey(K key) {
2133         Node<K,V> n = findNear(key, GT);
2134         return (n == null) ? null : n.key;
2135     }
2136 
2137     /**
2138      * Returns a key-value mapping associated with the least
2139      * key in this map, or <tt>null</tt> if the map is empty.
2140      * The returned entry does <em>not</em> support
2141      * the <tt>Entry.setValue</tt> method.
2142      */
2143     public Map.Entry<K,V> firstEntry() {
2144         for (;;) {
2145             Node<K,V> n = findFirst();
2146             if (n == null)
2147                 return null;
2148             AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
2149             if (e != null)
2150                 return e;
2151         }
2152     }
2153 
2154     /**
2155      * Returns a key-value mapping associated with the greatest
2156      * key in this map, or <tt>null</tt> if the map is empty.
2157      * The returned entry does <em>not</em> support
2158      * the <tt>Entry.setValue</tt> method.
2159      */
2160     public Map.Entry<K,V> lastEntry() {
2161         for (;;) {
2162             Node<K,V> n = findLast();
2163             if (n == null)
2164                 return null;
2165             AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
2166             if (e != null)
2167                 return e;
2168         }
2169     }
2170 
2171     /**
2172      * Removes and returns a key-value mapping associated with
2173      * the least key in this map, or <tt>null</tt> if the map is empty.
2174      * The returned entry does <em>not</em> support
2175      * the <tt>Entry.setValue</tt> method.
2176      */
2177     public Map.Entry<K,V> pollFirstEntry() {
2178         return doRemoveFirstEntry();
2179     }
2180 
2181     /**
2182      * Removes and returns a key-value mapping associated with
2183      * the greatest key in this map, or <tt>null</tt> if the map is empty.
2184      * The returned entry does <em>not</em> support
2185      * the <tt>Entry.setValue</tt> method.
2186      */
2187     public Map.Entry<K,V> pollLastEntry() {
2188         return doRemoveLastEntry();
2189     }
2190 
2191 
2192     /* ---------------- Iterators -------------- */
2193 
2194     /**
2195      * Base of iterator classes:
2196      */
2197     abstract class Iter<T> implements Iterator<T> {
2198         /** the last node returned by next() */
2199         Node<K,V> lastReturned;
2200         /** the next node to return from next(); */
2201         Node<K,V> next;
2202         /** Cache of next value field to maintain weak consistency */
2203         V nextValue;
2204 
2205         /** Initializes ascending iterator for entire range. */
2206         Iter() {
2207             for (;;) {
2208                 next = findFirst();
2209                 if (next == null)
2210                     break;
2211                 Object x = next.value;
2212                 if (x != null && x != next) {
2213                     nextValue = (V) x;
2214                     break;
2215                 }
2216             }
2217         }
2218 
2219         public final boolean hasNext() {
2220             return next != null;
2221         }
2222 
2223         /** Advances next to higher entry. */
2224         final void advance() {
2225             if (next == null)
2226                 throw new NoSuchElementException();
2227             lastReturned = next;
2228             for (;;) {
2229                 next = next.next;
2230                 if (next == null)
2231                     break;
2232                 Object x = next.value;
2233                 if (x != null && x != next) {
2234                     nextValue = (V) x;
2235                     break;
2236                 }
2237             }
2238         }
2239 
2240         public void remove() {
2241             Node<K,V> l = lastReturned;
2242             if (l == null)
2243                 throw new IllegalStateException();
2244             // It would not be worth all of the overhead to directly
2245             // unlink from here. Using remove is fast enough.
2246             ConcurrentSkipListMap.this.remove(l.key);
2247             lastReturned = null;
2248         }
2249 
2250     }
2251 
2252     final class ValueIterator extends Iter<V> {
2253         public V next() {
2254             V v = nextValue;
2255             advance();
2256             return v;
2257         }
2258     }
2259 
2260     final class KeyIterator extends Iter<K> {
2261         public K next() {
2262             Node<K,V> n = next;
2263             advance();
2264             return n.key;
2265         }
2266     }
2267 
2268     final class EntryIterator extends Iter<Map.Entry<K,V>> {
2269         public Map.Entry<K,V> next() {
2270             Node<K,V> n = next;
2271             V v = nextValue;
2272             advance();
2273             return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
2274         }
2275     }
2276 
2277     // Factory methods for iterators needed by ConcurrentSkipListSet etc
2278 
2279     Iterator<K> keyIterator() {
2280         return new KeyIterator();
2281     }
2282 
2283     Iterator<V> valueIterator() {
2284         return new ValueIterator();
2285     }
2286 
2287     Iterator<Map.Entry<K,V>> entryIterator() {
2288         return new EntryIterator();
2289     }
2290 
2291     /* ---------------- View Classes -------------- */
2292 
2293     /*
2294      * View classes are static, delegating to a ConcurrentNavigableMap
2295      * to allow use by SubMaps, which outweighs the ugliness of
2296      * needing type-tests for Iterator methods.
2297      */
2298 
2299     static final <E> List<E> toList(Collection<E> c) {
2300         // Using size() here would be a pessimization.
2301         List<E> list = new ArrayList<E>();
2302         for (E e : c)
2303             list.add(e);
2304         return list;
2305     }
2306 
2307     static final class KeySet<E>
2308             extends AbstractSet<E> implements NavigableSet<E> {
2309         private final ConcurrentNavigableMap<E,?> m;
2310         KeySet(ConcurrentNavigableMap<E,?> map) { m = map; }
2311         public int size() { return m.size(); }
2312         public boolean isEmpty() { return m.isEmpty(); }
2313         public boolean contains(Object o) { return m.containsKey(o); }
2314         public boolean remove(Object o) { return m.remove(o) != null; }
2315         public void clear() { m.clear(); }
2316         public E lower(E e) { return m.lowerKey(e); }
2317         public E floor(E e) { return m.floorKey(e); }
2318         public E ceiling(E e) { return m.ceilingKey(e); }
2319         public E higher(E e) { return m.higherKey(e); }
2320         public Comparator<? super E> comparator() { return m.comparator(); }
2321         public E first() { return m.firstKey(); }
2322         public E last() { return m.lastKey(); }
2323         public E pollFirst() {
2324             Map.Entry<E,?> e = m.pollFirstEntry();
2325             return (e == null) ? null : e.getKey();
2326         }
2327         public E pollLast() {
2328             Map.Entry<E,?> e = m.pollLastEntry();
2329             return (e == null) ? null : e.getKey();
2330         }
2331         public Iterator<E> iterator() {
2332             if (m instanceof ConcurrentSkipListMap)
2333                 return ((ConcurrentSkipListMap<E,Object>)m).keyIterator();
2334             else
2335                 return ((ConcurrentSkipListMap.SubMap<E,Object>)m).keyIterator();
2336         }
2337         public boolean equals(Object o) {
2338             if (o == this)
2339                 return true;
2340             if (!(o instanceof Set))
2341                 return false;
2342             Collection<?> c = (Collection<?>) o;
2343             try {
2344                 return containsAll(c) && c.containsAll(this);
2345             } catch (ClassCastException unused)   {
2346                 return false;
2347             } catch (NullPointerException unused) {
2348                 return false;
2349             }
2350         }
2351         public Object[] toArray()     { return toList(this).toArray();  }
2352         public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
2353         public Iterator<E> descendingIterator() {
2354             return descendingSet().iterator();
2355         }
2356         public NavigableSet<E> subSet(E fromElement,
2357                                       boolean fromInclusive,
2358                                       E toElement,
2359                                       boolean toInclusive) {
2360             return new KeySet<E>(m.subMap(fromElement, fromInclusive,
2361                                           toElement,   toInclusive));
2362         }
2363         public NavigableSet<E> headSet(E toElement, boolean inclusive) {
2364             return new KeySet<E>(m.headMap(toElement, inclusive));
2365         }
2366         public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
2367             return new KeySet<E>(m.tailMap(fromElement, inclusive));
2368         }
2369         public NavigableSet<E> subSet(E fromElement, E toElement) {
2370             return subSet(fromElement, true, toElement, false);
2371         }
2372         public NavigableSet<E> headSet(E toElement) {
2373             return headSet(toElement, false);
2374         }
2375         public NavigableSet<E> tailSet(E fromElement) {
2376             return tailSet(fromElement, true);
2377         }
2378         public NavigableSet<E> descendingSet() {
2379             return new KeySet<E>(m.descendingMap());
2380         }
2381     }
2382 
2383     static final class Values<E> extends AbstractCollection<E> {
2384         private final ConcurrentNavigableMap<?, E> m;
2385         Values(ConcurrentNavigableMap<?, E> map) {
2386             m = map;
2387         }
2388         public Iterator<E> iterator() {
2389             if (m instanceof ConcurrentSkipListMap)
2390                 return ((ConcurrentSkipListMap<?,E>)m).valueIterator();
2391             else
2392                 return ((SubMap<?,E>)m).valueIterator();
2393         }
2394         public boolean isEmpty() {
2395             return m.isEmpty();
2396         }
2397         public int size() {
2398             return m.size();
2399         }
2400         public boolean contains(Object o) {
2401             return m.containsValue(o);
2402         }
2403         public void clear() {
2404             m.clear();
2405         }
2406         public Object[] toArray()     { return toList(this).toArray();  }
2407         public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
2408     }
2409 
2410     static final class EntrySet<K1,V1> extends AbstractSet<Map.Entry<K1,V1>> {
2411         private final ConcurrentNavigableMap<K1, V1> m;
2412         EntrySet(ConcurrentNavigableMap<K1, V1> map) {
2413             m = map;
2414         }
2415 
2416         public Iterator<Map.Entry<K1,V1>> iterator() {
2417             if (m instanceof ConcurrentSkipListMap)
2418                 return ((ConcurrentSkipListMap<K1,V1>)m).entryIterator();
2419             else
2420                 return ((SubMap<K1,V1>)m).entryIterator();
2421         }
2422 
2423         public boolean contains(Object o) {
2424             if (!(o instanceof Map.Entry))
2425                 return false;
2426             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
2427             V1 v = m.get(e.getKey());
2428             return v != null && v.equals(e.getValue());
2429         }
2430         public boolean remove(Object o) {
2431             if (!(o instanceof Map.Entry))
2432                 return false;
2433             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
2434             return m.remove(e.getKey(),
2435                             e.getValue());
2436         }
2437         public boolean isEmpty() {
2438             return m.isEmpty();
2439         }
2440         public int size() {
2441             return m.size();
2442         }
2443         public void clear() {
2444             m.clear();
2445         }
2446         public boolean equals(Object o) {
2447             if (o == this)
2448                 return true;
2449             if (!(o instanceof Set))
2450                 return false;
2451             Collection<?> c = (Collection<?>) o;
2452             try {
2453                 return containsAll(c) && c.containsAll(this);
2454             } catch (ClassCastException unused)   {
2455                 return false;
2456             } catch (NullPointerException unused) {
2457                 return false;
2458             }
2459         }
2460         public Object[] toArray()     { return toList(this).toArray();  }
2461         public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
2462     }
2463 
2464     /**
2465      * Submaps returned by {@link ConcurrentSkipListMap} submap operations
2466      * represent a subrange of mappings of their underlying
2467      * maps. Instances of this class support all methods of their
2468      * underlying maps, differing in that mappings outside their range are
2469      * ignored, and attempts to add mappings outside their ranges result
2470      * in {@link IllegalArgumentException}.  Instances of this class are
2471      * constructed only using the <tt>subMap</tt>, <tt>headMap</tt>, and
2472      * <tt>tailMap</tt> methods of their underlying maps.
2473      *
2474      * @serial include
2475      */
2476     static final class SubMap<K,V> extends AbstractMap<K,V>
2477         implements ConcurrentNavigableMap<K,V>, Cloneable,
2478                    java.io.Serializable {
2479         private static final long serialVersionUID = -7647078645895051609L;
2480 
2481         /** Underlying map */
2482         private final ConcurrentSkipListMap<K,V> m;
2483         /** lower bound key, or null if from start */
2484         private final K lo;
2485         /** upper bound key, or null if to end */
2486         private final K hi;
2487         /** inclusion flag for lo */
2488         private final boolean loInclusive;
2489         /** inclusion flag for hi */
2490         private final boolean hiInclusive;
2491         /** direction */
2492         private final boolean isDescending;
2493 
2494         // Lazily initialized view holders
2495         private transient KeySet<K> keySetView;
2496         private transient Set<Map.Entry<K,V>> entrySetView;
2497         private transient Collection<V> valuesView;
2498 
2499         /**
2500          * Creates a new submap, initializing all fields
2501          */
2502         SubMap(ConcurrentSkipListMap<K,V> map,
2503                K fromKey, boolean fromInclusive,
2504                K toKey, boolean toInclusive,
2505                boolean isDescending) {
2506             if (fromKey != null && toKey != null &&
2507                 map.compare(fromKey, toKey) > 0)
2508                 throw new IllegalArgumentException("inconsistent range");
2509             this.m = map;
2510             this.lo = fromKey;
2511             this.hi = toKey;
2512             this.loInclusive = fromInclusive;
2513             this.hiInclusive = toInclusive;
2514             this.isDescending = isDescending;
2515         }
2516 
2517         /* ----------------  Utilities -------------- */
2518 
2519         private boolean tooLow(K key) {
2520             if (lo != null) {
2521                 int c = m.compare(key, lo);
2522                 if (c < 0 || (c == 0 && !loInclusive))
2523                     return true;
2524             }
2525             return false;
2526         }
2527 
2528         private boolean tooHigh(K key) {
2529             if (hi != null) {
2530                 int c = m.compare(key, hi);
2531                 if (c > 0 || (c == 0 && !hiInclusive))
2532                     return true;
2533             }
2534             return false;
2535         }
2536 
2537         private boolean inBounds(K key) {
2538             return !tooLow(key) && !tooHigh(key);
2539         }
2540 
2541         private void checkKeyBounds(K key) throws IllegalArgumentException {
2542             if (key == null)
2543                 throw new NullPointerException();
2544             if (!inBounds(key))
2545                 throw new IllegalArgumentException("key out of range");
2546         }
2547 
2548         /**
2549          * Returns true if node key is less than upper bound of range
2550          */
2551         private boolean isBeforeEnd(ConcurrentSkipListMap.Node<K,V> n) {
2552             if (n == null)
2553                 return false;
2554             if (hi == null)
2555                 return true;
2556             K k = n.key;
2557             if (k == null) // pass by markers and headers
2558                 return true;
2559             int c = m.compare(k, hi);
2560             if (c > 0 || (c == 0 && !hiInclusive))
2561                 return false;
2562             return true;
2563         }
2564 
2565         /**
2566          * Returns lowest node. This node might not be in range, so
2567          * most usages need to check bounds
2568          */
2569         private ConcurrentSkipListMap.Node<K,V> loNode() {
2570             if (lo == null)
2571                 return m.findFirst();
2572             else if (loInclusive)
2573                 return m.findNear(lo, GT|EQ);
2574             else
2575                 return m.findNear(lo, GT);
2576         }
2577 
2578         /**
2579          * Returns highest node. This node might not be in range, so
2580          * most usages need to check bounds
2581          */
2582         private ConcurrentSkipListMap.Node<K,V> hiNode() {
2583             if (hi == null)
2584                 return m.findLast();
2585             else if (hiInclusive)
2586                 return m.findNear(hi, LT|EQ);
2587             else
2588                 return m.findNear(hi, LT);
2589         }
2590 
2591         /**
2592          * Returns lowest absolute key (ignoring directonality)
2593          */
2594         private K lowestKey() {
2595             ConcurrentSkipListMap.Node<K,V> n = loNode();
2596             if (isBeforeEnd(n))
2597                 return n.key;
2598             else
2599                 throw new NoSuchElementException();
2600         }
2601 
2602         /**
2603          * Returns highest absolute key (ignoring directonality)
2604          */
2605         private K highestKey() {
2606             ConcurrentSkipListMap.Node<K,V> n = hiNode();
2607             if (n != null) {
2608                 K last = n.key;
2609                 if (inBounds(last))
2610                     return last;
2611             }
2612             throw new NoSuchElementException();
2613         }
2614 
2615         private Map.Entry<K,V> lowestEntry() {
2616             for (;;) {
2617                 ConcurrentSkipListMap.Node<K,V> n = loNode();
2618                 if (!isBeforeEnd(n))
2619                     return null;
2620                 Map.Entry<K,V> e = n.createSnapshot();
2621                 if (e != null)
2622                     return e;
2623             }
2624         }
2625 
2626         private Map.Entry<K,V> highestEntry() {
2627             for (;;) {
2628                 ConcurrentSkipListMap.Node<K,V> n = hiNode();
2629                 if (n == null || !inBounds(n.key))
2630                     return null;
2631                 Map.Entry<K,V> e = n.createSnapshot();
2632                 if (e != null)
2633                     return e;
2634             }
2635         }
2636 
2637         private Map.Entry<K,V> removeLowest() {
2638             for (;;) {
2639                 Node<K,V> n = loNode();
2640                 if (n == null)
2641                     return null;
2642                 K k = n.key;
2643                 if (!inBounds(k))
2644                     return null;
2645                 V v = m.doRemove(k, null);
2646                 if (v != null)
2647                     return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2648             }
2649         }
2650 
2651         private Map.Entry<K,V> removeHighest() {
2652             for (;;) {
2653                 Node<K,V> n = hiNode();
2654                 if (n == null)
2655                     return null;
2656                 K k = n.key;
2657                 if (!inBounds(k))
2658                     return null;
2659                 V v = m.doRemove(k, null);
2660                 if (v != null)
2661                     return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2662             }
2663         }
2664 
2665         /**
2666          * Submap version of ConcurrentSkipListMap.getNearEntry
2667          */
2668         private Map.Entry<K,V> getNearEntry(K key, int rel) {
2669             if (isDescending) { // adjust relation for direction
2670                 if ((rel & LT) == 0)
2671                     rel |= LT;
2672                 else
2673                     rel &= ~LT;
2674             }
2675             if (tooLow(key))
2676                 return ((rel & LT) != 0) ? null : lowestEntry();
2677             if (tooHigh(key))
2678                 return ((rel & LT) != 0) ? highestEntry() : null;
2679             for (;;) {
2680                 Node<K,V> n = m.findNear(key, rel);
2681                 if (n == null || !inBounds(n.key))
2682                     return null;
2683                 K k = n.key;
2684                 V v = n.getValidValue();
2685                 if (v != null)
2686                     return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2687             }
2688         }
2689 
2690         // Almost the same as getNearEntry, except for keys
2691         private K getNearKey(K key, int rel) {
2692             if (isDescending) { // adjust relation for direction
2693                 if ((rel & LT) == 0)
2694                     rel |= LT;
2695                 else
2696                     rel &= ~LT;
2697             }
2698             if (tooLow(key)) {
2699                 if ((rel & LT) == 0) {
2700                     ConcurrentSkipListMap.Node<K,V> n = loNode();
2701                     if (isBeforeEnd(n))
2702                         return n.key;
2703                 }
2704                 return null;
2705             }
2706             if (tooHigh(key)) {
2707                 if ((rel & LT) != 0) {
2708                     ConcurrentSkipListMap.Node<K,V> n = hiNode();
2709                     if (n != null) {
2710                         K last = n.key;
2711                         if (inBounds(last))
2712                             return last;
2713                     }
2714                 }
2715                 return null;
2716             }
2717             for (;;) {
2718                 Node<K,V> n = m.findNear(key, rel);
2719                 if (n == null || !inBounds(n.key))
2720                     return null;
2721                 K k = n.key;
2722                 V v = n.getValidValue();
2723                 if (v != null)
2724                     return k;
2725             }
2726         }
2727 
2728         /* ----------------  Map API methods -------------- */
2729 
2730         public boolean containsKey(Object key) {
2731             if (key == null) throw new NullPointerException();
2732             K k = (K)key;
2733             return inBounds(k) && m.containsKey(k);
2734         }
2735 
2736         public V get(Object key) {
2737             if (key == null) throw new NullPointerException();
2738             K k = (K)key;
2739             return (!inBounds(k)) ? null : m.get(k);
2740         }
2741 
2742         public V put(K key, V value) {
2743             checkKeyBounds(key);
2744             return m.put(key, value);
2745         }
2746 
2747         public V remove(Object key) {
2748             K k = (K)key;
2749             return (!inBounds(k)) ? null : m.remove(k);
2750         }
2751 
2752         public int size() {
2753             long count = 0;
2754             for (ConcurrentSkipListMap.Node<K,V> n = loNode();
2755                  isBeforeEnd(n);
2756                  n = n.next) {
2757                 if (n.getValidValue() != null)
2758                     ++count;
2759             }
2760             return count >= Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)count;
2761         }
2762 
2763         public boolean isEmpty() {
2764             return !isBeforeEnd(loNode());
2765         }
2766 
2767         public boolean containsValue(Object value) {
2768             if (value == null)
2769                 throw new NullPointerException();
2770             for (ConcurrentSkipListMap.Node<K,V> n = loNode();
2771                  isBeforeEnd(n);
2772                  n = n.next) {
2773                 V v = n.getValidValue();
2774                 if (v != null && value.equals(v))
2775                     return true;
2776             }
2777             return false;
2778         }
2779 
2780         public void clear() {
2781             for (ConcurrentSkipListMap.Node<K,V> n = loNode();
2782                  isBeforeEnd(n);
2783                  n = n.next) {
2784                 if (n.getValidValue() != null)
2785                     m.remove(n.key);
2786             }
2787         }
2788 
2789         /* ----------------  ConcurrentMap API methods -------------- */
2790 
2791         public V putIfAbsent(K key, V value) {
2792             checkKeyBounds(key);
2793             return m.putIfAbsent(key, value);
2794         }
2795 
2796         public boolean remove(Object key, Object value) {
2797             K k = (K)key;
2798             return inBounds(k) && m.remove(k, value);
2799         }
2800 
2801         public boolean replace(K key, V oldValue, V newValue) {
2802             checkKeyBounds(key);
2803             return m.replace(key, oldValue, newValue);
2804         }
2805 
2806         public V replace(K key, V value) {
2807             checkKeyBounds(key);
2808             return m.replace(key, value);
2809         }
2810 
2811         /* ----------------  SortedMap API methods -------------- */
2812 
2813         public Comparator<? super K> comparator() {
2814             Comparator<? super K> cmp = m.comparator();
2815             if (isDescending)
2816                 return Collections.reverseOrder(cmp);
2817             else
2818                 return cmp;
2819         }
2820 
2821         /**
2822          * Utility to create submaps, where given bounds override
2823          * unbounded(null) ones and/or are checked against bounded ones.
2824          */
2825         private SubMap<K,V> newSubMap(K fromKey,
2826                                       boolean fromInclusive,
2827                                       K toKey,
2828                                       boolean toInclusive) {
2829             if (isDescending) { // flip senses
2830                 K tk = fromKey;
2831                 fromKey = toKey;
2832                 toKey = tk;
2833                 boolean ti = fromInclusive;
2834                 fromInclusive = toInclusive;
2835                 toInclusive = ti;
2836             }
2837             if (lo != null) {
2838                 if (fromKey == null) {
2839                     fromKey = lo;
2840                     fromInclusive = loInclusive;
2841                 }
2842                 else {
2843                     int c = m.compare(fromKey, lo);
2844                     if (c < 0 || (c == 0 && !loInclusive && fromInclusive))
2845                         throw new IllegalArgumentException("key out of range");
2846                 }
2847             }
2848             if (hi != null) {
2849                 if (toKey == null) {
2850                     toKey = hi;
2851                     toInclusive = hiInclusive;
2852                 }
2853                 else {
2854                     int c = m.compare(toKey, hi);
2855                     if (c > 0 || (c == 0 && !hiInclusive && toInclusive))
2856                         throw new IllegalArgumentException("key out of range");
2857                 }
2858             }
2859             return new SubMap<K,V>(m, fromKey, fromInclusive,
2860                                    toKey, toInclusive, isDescending);
2861         }
2862 
2863         public SubMap<K,V> subMap(K fromKey,
2864                                   boolean fromInclusive,
2865                                   K toKey,
2866                                   boolean toInclusive) {
2867             if (fromKey == null || toKey == null)
2868                 throw new NullPointerException();
2869             return newSubMap(fromKey, fromInclusive, toKey, toInclusive);
2870         }
2871 
2872         public SubMap<K,V> headMap(K toKey,
2873                                    boolean inclusive) {
2874             if (toKey == null)
2875                 throw new NullPointerException();
2876             return newSubMap(null, false, toKey, inclusive);
2877         }
2878 
2879         public SubMap<K,V> tailMap(K fromKey,
2880                                    boolean inclusive) {
2881             if (fromKey == null)
2882                 throw new NullPointerException();
2883             return newSubMap(fromKey, inclusive, null, false);
2884         }
2885 
2886         public SubMap<K,V> subMap(K fromKey, K toKey) {
2887             return subMap(fromKey, true, toKey, false);
2888         }
2889 
2890         public SubMap<K,V> headMap(K toKey) {
2891             return headMap(toKey, false);
2892         }
2893 
2894         public SubMap<K,V> tailMap(K fromKey) {
2895             return tailMap(fromKey, true);
2896         }
2897 
2898         public SubMap<K,V> descendingMap() {
2899             return new SubMap<K,V>(m, lo, loInclusive,
2900                                    hi, hiInclusive, !isDescending);
2901         }
2902 
2903         /* ----------------  Relational methods -------------- */
2904 
2905         public Map.Entry<K,V> ceilingEntry(K key) {
2906             return getNearEntry(key, GT|EQ);
2907         }
2908 
2909         public K ceilingKey(K key) {
2910             return getNearKey(key, GT|EQ);
2911         }
2912 
2913         public Map.Entry<K,V> lowerEntry(K key) {
2914             return getNearEntry(key, LT);
2915         }
2916 
2917         public K lowerKey(K key) {
2918             return getNearKey(key, LT);
2919         }
2920 
2921         public Map.Entry<K,V> floorEntry(K key) {
2922             return getNearEntry(key, LT|EQ);
2923         }
2924 
2925         public K floorKey(K key) {
2926             return getNearKey(key, LT|EQ);
2927         }
2928 
2929         public Map.Entry<K,V> higherEntry(K key) {
2930             return getNearEntry(key, GT);
2931         }
2932 
2933         public K higherKey(K key) {
2934             return getNearKey(key, GT);
2935         }
2936 
2937         public K firstKey() {
2938             return isDescending ? highestKey() : lowestKey();
2939         }
2940 
2941         public K lastKey() {
2942             return isDescending ? lowestKey() : highestKey();
2943         }
2944 
2945         public Map.Entry<K,V> firstEntry() {
2946             return isDescending ? highestEntry() : lowestEntry();
2947         }
2948 
2949         public Map.Entry<K,V> lastEntry() {
2950             return isDescending ? lowestEntry() : highestEntry();
2951         }
2952 
2953         public Map.Entry<K,V> pollFirstEntry() {
2954             return isDescending ? removeHighest() : removeLowest();
2955         }
2956 
2957         public Map.Entry<K,V> pollLastEntry() {
2958             return isDescending ? removeLowest() : removeHighest();
2959         }
2960 
2961         /* ---------------- Submap Views -------------- */
2962 
2963         public NavigableSet<K> keySet() {
2964             KeySet<K> ks = keySetView;
2965             return (ks != null) ? ks : (keySetView = new KeySet<K>(this));
2966         }
2967 
2968         public NavigableSet<K> navigableKeySet() {
2969             KeySet<K> ks = keySetView;
2970             return (ks != null) ? ks : (keySetView = new KeySet<K>(this));
2971         }
2972 
2973         public Collection<V> values() {
2974             Collection<V> vs = valuesView;
2975             return (vs != null) ? vs : (valuesView = new Values<V>(this));
2976         }
2977 
2978         public Set<Map.Entry<K,V>> entrySet() {
2979             Set<Map.Entry<K,V>> es = entrySetView;
2980             return (es != null) ? es : (entrySetView = new EntrySet<K,V>(this));
2981         }
2982 
2983         public NavigableSet<K> descendingKeySet() {
2984             return descendingMap().navigableKeySet();
2985         }
2986 
2987         Iterator<K> keyIterator() {
2988             return new SubMapKeyIterator();
2989         }
2990 
2991         Iterator<V> valueIterator() {
2992             return new SubMapValueIterator();
2993         }
2994 
2995         Iterator<Map.Entry<K,V>> entryIterator() {
2996             return new SubMapEntryIterator();
2997         }
2998 
2999         /**
3000          * Variant of main Iter class to traverse through submaps.
3001          */
3002         abstract class SubMapIter<T> implements Iterator<T> {
3003             /** the last node returned by next() */
3004             Node<K,V> lastReturned;
3005             /** the next node to return from next(); */
3006             Node<K,V> next;
3007             /** Cache of next value field to maintain weak consistency */
3008             V nextValue;
3009 
3010             SubMapIter() {
3011                 for (;;) {
3012                     next = isDescending ? hiNode() : loNode();
3013                     if (next == null)
3014                         break;
3015                     Object x = next.value;
3016                     if (x != null && x != next) {
3017                         if (! inBounds(next.key))
3018                             next = null;
3019                         else
3020                             nextValue = (V) x;
3021                         break;
3022                     }
3023                 }
3024             }
3025 
3026             public final boolean hasNext() {
3027                 return next != null;
3028             }
3029 
3030             final void advance() {
3031                 if (next == null)
3032                     throw new NoSuchElementException();
3033                 lastReturned = next;
3034                 if (isDescending)
3035                     descend();
3036                 else
3037                     ascend();
3038             }
3039 
3040             private void ascend() {
3041                 for (;;) {
3042                     next = next.next;
3043                     if (next == null)
3044                         break;
3045                     Object x = next.value;
3046                     if (x != null && x != next) {
3047                         if (tooHigh(next.key))
3048                             next = null;
3049                         else
3050                             nextValue = (V) x;
3051                         break;
3052                     }
3053                 }
3054             }
3055 
3056             private void descend() {
3057                 for (;;) {
3058                     next = m.findNear(lastReturned.key, LT);
3059                     if (next == null)
3060                         break;
3061                     Object x = next.value;
3062                     if (x != null && x != next) {
3063                         if (tooLow(next.key))
3064                             next = null;
3065                         else
3066                             nextValue = (V) x;
3067                         break;
3068                     }
3069                 }
3070             }
3071 
3072             public void remove() {
3073                 Node<K,V> l = lastReturned;
3074                 if (l == null)
3075                     throw new IllegalStateException();
3076                 m.remove(l.key);
3077                 lastReturned = null;
3078             }
3079 
3080         }
3081 
3082         final class SubMapValueIterator extends SubMapIter<V> {
3083             public V next() {
3084                 V v = nextValue;
3085                 advance();
3086                 return v;
3087             }
3088         }
3089 
3090         final class SubMapKeyIterator extends SubMapIter<K> {
3091             public K next() {
3092                 Node<K,V> n = next;
3093                 advance();
3094                 return n.key;
3095             }
3096         }
3097 
3098         final class SubMapEntryIterator extends SubMapIter<Map.Entry<K,V>> {
3099             public Map.Entry<K,V> next() {
3100                 Node<K,V> n = next;
3101                 V v = nextValue;
3102                 advance();
3103                 return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
3104             }
3105         }
3106     }
3107 
3108     // Unsafe mechanics
3109     private static final sun.misc.Unsafe UNSAFE;
3110     private static final long headOffset;
3111     static {
3112         try {
3113             UNSAFE = sun.misc.Unsafe.getUnsafe();
3114             Class<?> k = ConcurrentSkipListMap.class;
3115             headOffset = UNSAFE.objectFieldOffset
3116                 (k.getDeclaredField("head"));
3117         } catch (Exception e) {
3118             throw new Error(e);
3119         }
3120     }
3121 }
--- EOF ---