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/licenses/publicdomain
  34  */
  35 
  36 package java.util.concurrent;
  37 import java.util.*;
  38 import java.util.concurrent.atomic.*;
  39 
  40 /**
  41  * A scalable concurrent {@link ConcurrentNavigableMap} implementation.
  42  * The map is sorted according to the {@linkplain Comparable natural
  43  * ordering} of its keys, or by a {@link Comparator} provided at map
  44  * creation time, depending on which constructor is used.
  45  *
  46  * <p>This class implements a concurrent variant of <a
  47  * href="http://www.cs.umd.edu/~pugh/">SkipLists</a> providing
  48  * expected average <i>log(n)</i> time cost for the
  49  * <tt>containsKey</tt>, <tt>get</tt>, <tt>put</tt> and
  50  * <tt>remove</tt> operations and their variants.  Insertion, removal,
  51  * update, and access operations safely execute concurrently by
  52  * multiple threads.  Iterators are <i>weakly consistent</i>, returning
  53  * elements reflecting the state of the map at some point at or since
  54  * the creation of the iterator.  They do <em>not</em> throw {@link
  55  * ConcurrentModificationException}, and may proceed concurrently with
  56  * other operations. Ascending key ordered views and their iterators
  57  * are faster than descending ones.
  58  *
  59  * <p>All <tt>Map.Entry</tt> pairs returned by methods in this class
  60  * and its views represent snapshots of mappings at the time they were
  61  * produced. They do <em>not</em> support the <tt>Entry.setValue</tt>
  62  * method. (Note however that it is possible to change mappings in the
  63  * associated map using <tt>put</tt>, <tt>putIfAbsent</tt>, or
  64  * <tt>replace</tt>, depending on exactly which effect you need.)
  65  *
  66  * <p>Beware that, unlike in most collections, the <tt>size</tt>
  67  * method is <em>not</em> a constant-time operation. Because of the
  68  * asynchronous nature of these maps, determining the current number
  69  * of elements requires a traversal of the elements.  Additionally,
  70  * the bulk operations <tt>putAll</tt>, <tt>equals</tt>, and
  71  * <tt>clear</tt> are <em>not</em> guaranteed to be performed
  72  * atomically. For example, an iterator operating concurrently with a
  73  * <tt>putAll</tt> operation might view only some of the added
  74  * 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 public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
  93     implements ConcurrentNavigableMap<K,V>,
  94                Cloneable,
  95                java.io.Serializable {
  96     /*
  97      * This class implements a tree-like two-dimensionally linked skip
  98      * list in which the index levels are represented in separate
  99      * nodes from the base nodes holding data.  There are two reasons
 100      * for taking this approach instead of the usual array-based
 101      * structure: 1) Array based implementations seem to encounter
 102      * more complexity and overhead 2) We can use cheaper algorithms
 103      * for the heavily-traversed index lists than can be used for the
 104      * base lists.  Here's a picture of some of the basics for a
 105      * possible list with 2 levels of index:
 106      *
 107      * Head nodes          Index nodes
 108      * +-+    right        +-+                      +-+
 109      * |2|---------------->| |--------------------->| |->null
 110      * +-+                 +-+                      +-+
 111      *  | down              |                        |
 112      *  v                   v                        v
 113      * +-+            +-+  +-+       +-+            +-+       +-+
 114      * |1|----------->| |->| |------>| |----------->| |------>| |->null
 115      * +-+            +-+  +-+       +-+            +-+       +-+
 116      *  v              |    |         |              |         |
 117      * Nodes  next     v    v         v              v         v
 118      * +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
 119      * | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null
 120      * +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
 121      *
 122      * The base lists use a variant of the HM linked ordered set
 123      * algorithm. See Tim Harris, "A pragmatic implementation of
 124      * non-blocking linked lists"
 125      * http://www.cl.cam.ac.uk/~tlh20/publications.html and Maged
 126      * Michael "High Performance Dynamic Lock-Free Hash Tables and
 127      * List-Based Sets"
 128      * http://www.research.ibm.com/people/m/michael/pubs.htm.  The
 129      * basic idea in these lists is to mark the "next" pointers of
 130      * deleted nodes when deleting to avoid conflicts with concurrent
 131      * insertions, and when traversing to keep track of triples
 132      * (predecessor, node, successor) in order to detect when and how
 133      * to unlink these deleted nodes.
 134      *
 135      * Rather than using mark-bits to mark list deletions (which can
 136      * be slow and space-intensive using AtomicMarkedReference), nodes
 137      * use direct CAS'able next pointers.  On deletion, instead of
 138      * marking a pointer, they splice in another node that can be
 139      * thought of as standing for a marked pointer (indicating this by
 140      * using otherwise impossible field values).  Using plain nodes
 141      * acts roughly like "boxed" implementations of marked pointers,
 142      * but uses new nodes only when nodes are deleted, not for every
 143      * link.  This requires less space and supports faster
 144      * traversal. Even if marked references were better supported by
 145      * JVMs, traversal using this technique might still be faster
 146      * because any search need only read ahead one more node than
 147      * otherwise required (to check for trailing marker) rather than
 148      * unmasking mark bits or whatever on each read.
 149      *
 150      * This approach maintains the essential property needed in the HM
 151      * algorithm of changing the next-pointer of a deleted node so
 152      * that any other CAS of it will fail, but implements the idea by
 153      * changing the pointer to point to a different node, not by
 154      * marking it.  While it would be possible to further squeeze
 155      * space by defining marker nodes not to have key/value fields, it
 156      * isn't worth the extra type-testing overhead.  The deletion
 157      * markers are rarely encountered during traversal and are
 158      * normally quickly garbage collected. (Note that this technique
 159      * would not work well in systems without garbage collection.)
 160      *
 161      * In addition to using deletion markers, the lists also use
 162      * nullness of value fields to indicate deletion, in a style
 163      * similar to typical lazy-deletion schemes.  If a node's value is
 164      * null, then it is considered logically deleted and ignored even
 165      * though it is still reachable. This maintains proper control of
 166      * concurrent replace vs delete operations -- an attempted replace
 167      * must fail if a delete beat it by nulling field, and a delete
 168      * must return the last non-null value held in the field. (Note:
 169      * Null, rather than some special marker, is used for value fields
 170      * here because it just so happens to mesh with the Map API
 171      * requirement that method get returns null if there is no
 172      * mapping, which allows nodes to remain concurrently readable
 173      * even when deleted. Using any other marker value here would be
 174      * messy at best.)
 175      *
 176      * Here's the sequence of events for a deletion of node n with
 177      * predecessor b and successor f, initially:
 178      *
 179      *        +------+       +------+      +------+
 180      *   ...  |   b  |------>|   n  |----->|   f  | ...
 181      *        +------+       +------+      +------+
 182      *
 183      * 1. CAS n's value field from non-null to null.
 184      *    From this point on, no public operations encountering
 185      *    the node consider this mapping to exist. However, other
 186      *    ongoing insertions and deletions might still modify
 187      *    n's next pointer.
 188      *
 189      * 2. CAS n's next pointer to point to a new marker node.
 190      *    From this point on, no other nodes can be appended to n.
 191      *    which avoids deletion errors in CAS-based linked lists.
 192      *
 193      *        +------+       +------+      +------+       +------+
 194      *   ...  |   b  |------>|   n  |----->|marker|------>|   f  | ...
 195      *        +------+       +------+      +------+       +------+
 196      *
 197      * 3. CAS b's next pointer over both n and its marker.
 198      *    From this point on, no new traversals will encounter n,
 199      *    and it can eventually be GCed.
 200      *        +------+                                    +------+
 201      *   ...  |   b  |----------------------------------->|   f  | ...
 202      *        +------+                                    +------+
 203      *
 204      * A failure at step 1 leads to simple retry due to a lost race
 205      * with another operation. Steps 2-3 can fail because some other
 206      * thread noticed during a traversal a node with null value and
 207      * helped out by marking and/or unlinking.  This helping-out
 208      * ensures that no thread can become stuck waiting for progress of
 209      * the deleting thread.  The use of marker nodes slightly
 210      * complicates helping-out code because traversals must track
 211      * consistent reads of up to four nodes (b, n, marker, f), not
 212      * just (b, n, f), although the next field of a marker is
 213      * immutable, and once a next field is CAS'ed to point to a
 214      * marker, it never again changes, so this requires less care.
 215      *
 216      * Skip lists add indexing to this scheme, so that the base-level
 217      * traversals start close to the locations being found, inserted
 218      * or deleted -- usually base level traversals only traverse a few
 219      * nodes. This doesn't change the basic algorithm except for the
 220      * need to make sure base traversals start at predecessors (here,
 221      * b) that are not (structurally) deleted, otherwise retrying
 222      * after processing the deletion.
 223      *
 224      * Index levels are maintained as lists with volatile next fields,
 225      * using CAS to link and unlink.  Races are allowed in index-list
 226      * operations that can (rarely) fail to link in a new index node
 227      * or delete one. (We can't do this of course for data nodes.)
 228      * However, even when this happens, the index lists remain sorted,
 229      * so correctly serve as indices.  This can impact performance,
 230      * but since skip lists are probabilistic anyway, the net result
 231      * is that under contention, the effective "p" value may be lower
 232      * than its nominal value. And race windows are kept small enough
 233      * that in practice these failures are rare, even under a lot of
 234      * contention.
 235      *
 236      * The fact that retries (for both base and index lists) are
 237      * relatively cheap due to indexing allows some minor
 238      * simplifications of retry logic. Traversal restarts are
 239      * performed after most "helping-out" CASes. This isn't always
 240      * strictly necessary, but the implicit backoffs tend to help
 241      * reduce other downstream failed CAS's enough to outweigh restart
 242      * cost.  This worsens the worst case, but seems to improve even
 243      * highly contended cases.
 244      *
 245      * Unlike most skip-list implementations, index insertion and
 246      * deletion here require a separate traversal pass occuring after
 247      * the base-level action, to add or remove index nodes.  This adds
 248      * to single-threaded overhead, but improves contended
 249      * multithreaded performance by narrowing interference windows,
 250      * and allows deletion to ensure that all index nodes will be made
 251      * unreachable upon return from a public remove operation, thus
 252      * avoiding unwanted garbage retention. This is more important
 253      * here than in some other data structures because we cannot null
 254      * out node fields referencing user keys since they might still be
 255      * read by other ongoing traversals.
 256      *
 257      * Indexing uses skip list parameters that maintain good search
 258      * performance while using sparser-than-usual indices: The
 259      * hardwired parameters k=1, p=0.5 (see method randomLevel) mean
 260      * that about one-quarter of the nodes have indices. Of those that
 261      * do, half have one level, a quarter have two, and so on (see
 262      * Pugh's Skip List Cookbook, sec 3.4).  The expected total space
 263      * requirement for a map is slightly less than for the current
 264      * implementation of java.util.TreeMap.
 265      *
 266      * Changing the level of the index (i.e, the height of the
 267      * tree-like structure) also uses CAS. The head index has initial
 268      * level/height of one. Creation of an index with height greater
 269      * than the current level adds a level to the head index by
 270      * CAS'ing on a new top-most head. To maintain good performance
 271      * after a lot of removals, deletion methods heuristically try to
 272      * reduce the height if the topmost levels appear to be empty.
 273      * This may encounter races in which it possible (but rare) to
 274      * reduce and "lose" a level just as it is about to contain an
 275      * index (that will then never be encountered). This does no
 276      * structural harm, and in practice appears to be a better option
 277      * than allowing unrestrained growth of levels.
 278      *
 279      * The code for all this is more verbose than you'd like. Most
 280      * operations entail locating an element (or position to insert an
 281      * element). The code to do this can't be nicely factored out
 282      * because subsequent uses require a snapshot of predecessor
 283      * and/or successor and/or value fields which can't be returned
 284      * all at once, at least not without creating yet another object
 285      * to hold them -- creating such little objects is an especially
 286      * bad idea for basic internal search operations because it adds
 287      * to GC overhead.  (This is one of the few times I've wished Java
 288      * had macros.) Instead, some traversal code is interleaved within
 289      * insertion and removal operations.  The control logic to handle
 290      * all the retry conditions is sometimes twisty. Most search is
 291      * broken into 2 parts. findPredecessor() searches index nodes
 292      * only, returning a base-level predecessor of the key. findNode()
 293      * finishes out the base-level search. Even with this factoring,
 294      * there is a fair amount of near-duplication of code to handle
 295      * variants.
 296      *
 297      * For explanation of algorithms sharing at least a couple of
 298      * features with this one, see Mikhail Fomitchev's thesis
 299      * (http://www.cs.yorku.ca/~mikhail/), Keir Fraser's thesis
 300      * (http://www.cl.cam.ac.uk/users/kaf24/), and Hakan Sundell's
 301      * thesis (http://www.cs.chalmers.se/~phs/).
 302      *
 303      * Given the use of tree-like index nodes, you might wonder why
 304      * this doesn't use some kind of search tree instead, which would
 305      * support somewhat faster search operations. The reason is that
 306      * there are no known efficient lock-free insertion and deletion
 307      * algorithms for search trees. The immutability of the "down"
 308      * links of index nodes (as opposed to mutable "left" fields in
 309      * true trees) makes this tractable using only CAS operations.
 310      *
 311      * Notation guide for local variables
 312      * Node:         b, n, f    for  predecessor, node, successor
 313      * Index:        q, r, d    for index node, right, down.
 314      *               t          for another index node
 315      * Head:         h
 316      * Levels:       j
 317      * Keys:         k, key
 318      * Values:       v, value
 319      * Comparisons:  c
 320      */
 321 
 322     private static final long serialVersionUID = -8627078645895051609L;
 323 
 324     /**
 325      * Generates the initial random seed for the cheaper per-instance
 326      * random number generators used in randomLevel.
 327      */
 328     private static final Random seedGenerator = new Random();
 329 
 330     /**
 331      * Special value used to identify base-level header
 332      */
 333     private static final Object BASE_HEADER = new Object();
 334 
 335     /**
 336      * The topmost head index of the skiplist.
 337      */
 338     private transient volatile HeadIndex<K,V> head;
 339 
 340     /**
 341      * The comparator used to maintain order in this map, or null
 342      * if using natural ordering.
 343      * @serial
 344      */
 345     private final Comparator<? super K> comparator;
 346 
 347     /**
 348      * Seed for simple random number generator.  Not volatile since it
 349      * doesn't matter too much if different threads don't see updates.
 350      */
 351     private transient int randomSeed;
 352 
 353     /** Lazily initialized key set */
 354     private transient KeySet keySet;
 355     /** Lazily initialized entry set */
 356     private transient EntrySet entrySet;
 357     /** Lazily initialized values collection */
 358     private transient Values values;
 359     /** Lazily initialized descending key set */
 360     private transient ConcurrentNavigableMap<K,V> descendingMap;
 361 
 362     /**
 363      * Initializes or resets state. Needed by constructors, clone,
 364      * clear, readObject. and ConcurrentSkipListSet.clone.
 365      * (Note that comparator must be separately initialized.)
 366      */
 367     final void initialize() {
 368         keySet = null;
 369         entrySet = null;
 370         values = null;
 371         descendingMap = null;
 372         randomSeed = seedGenerator.nextInt() | 0x0100; // ensure nonzero
 373         head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),
 374                                   null, null, 1);
 375     }
 376 
 377     /** Updater for casHead */
 378     private static final
 379         AtomicReferenceFieldUpdater<ConcurrentSkipListMap, HeadIndex>
 380         headUpdater = AtomicReferenceFieldUpdater.newUpdater
 381         (ConcurrentSkipListMap.class, HeadIndex.class, "head");
 382 
 383     /**
 384      * compareAndSet head node
 385      */
 386     private boolean casHead(HeadIndex<K,V> cmp, HeadIndex<K,V> val) {
 387         return headUpdater.compareAndSet(this, cmp, val);
 388     }
 389 
 390     /* ---------------- Nodes -------------- */
 391 
 392     /**
 393      * Nodes hold keys and values, and are singly linked in sorted
 394      * order, possibly with some intervening marker nodes. The list is
 395      * headed by a dummy node accessible as head.node. The value field
 396      * is declared only as Object because it takes special non-V
 397      * values for marker and header nodes.
 398      */
 399     static final class Node<K,V> {
 400         final K key;
 401         volatile Object value;
 402         volatile Node<K,V> next;
 403 
 404         /**
 405          * Creates a new regular node.
 406          */
 407         Node(K key, Object value, Node<K,V> next) {
 408             this.key = key;
 409             this.value = value;
 410             this.next = next;
 411         }
 412 
 413         /**
 414          * Creates a new marker node. A marker is distinguished by
 415          * having its value field point to itself.  Marker nodes also
 416          * have null keys, a fact that is exploited in a few places,
 417          * but this doesn't distinguish markers from the base-level
 418          * header node (head.node), which also has a null key.
 419          */
 420         Node(Node<K,V> next) {
 421             this.key = null;
 422             this.value = this;
 423             this.next = next;
 424         }
 425 
 426         /** Updater for casNext */
 427         static final AtomicReferenceFieldUpdater<Node, Node>
 428             nextUpdater = AtomicReferenceFieldUpdater.newUpdater
 429             (Node.class, Node.class, "next");
 430 
 431         /** Updater for casValue */
 432         static final AtomicReferenceFieldUpdater<Node, Object>
 433             valueUpdater = AtomicReferenceFieldUpdater.newUpdater
 434             (Node.class, Object.class, "value");
 435 
 436         /**
 437          * compareAndSet value field
 438          */
 439         boolean casValue(Object cmp, Object val) {
 440             return valueUpdater.compareAndSet(this, cmp, val);
 441         }
 442 
 443         /**
 444          * compareAndSet next field
 445          */
 446         boolean casNext(Node<K,V> cmp, Node<K,V> val) {
 447             return nextUpdater.compareAndSet(this, cmp, val);
 448         }
 449 
 450         /**
 451          * Returns true if this node is a marker. This method isn't
 452          * actually called in any current code checking for markers
 453          * because callers will have already read value field and need
 454          * to use that read (not another done here) and so directly
 455          * test if value points to node.
 456          * @param n a possibly null reference to a node
 457          * @return true if this node is a marker node
 458          */
 459         boolean isMarker() {
 460             return value == this;
 461         }
 462 
 463         /**
 464          * Returns true if this node is the header of base-level list.
 465          * @return true if this node is header node
 466          */
 467         boolean isBaseHeader() {
 468             return value == BASE_HEADER;
 469         }
 470 
 471         /**
 472          * Tries to append a deletion marker to this node.
 473          * @param f the assumed current successor of this node
 474          * @return true if successful
 475          */
 476         boolean appendMarker(Node<K,V> f) {
 477             return casNext(f, new Node<K,V>(f));
 478         }
 479 
 480         /**
 481          * Helps out a deletion by appending marker or unlinking from
 482          * predecessor. This is called during traversals when value
 483          * field seen to be null.
 484          * @param b predecessor
 485          * @param f successor
 486          */
 487         void helpDelete(Node<K,V> b, Node<K,V> f) {
 488             /*
 489              * Rechecking links and then doing only one of the
 490              * help-out stages per call tends to minimize CAS
 491              * interference among helping threads.
 492              */
 493             if (f == next && this == b.next) {
 494                 if (f == null || f.value != f) // not already marked
 495                     appendMarker(f);
 496                 else
 497                     b.casNext(this, f.next);
 498             }
 499         }
 500 
 501         /**
 502          * Returns value if this node contains a valid key-value pair,
 503          * else null.
 504          * @return this node's value if it isn't a marker or header or
 505          * is deleted, else null.
 506          */
 507         V getValidValue() {
 508             Object v = value;
 509             if (v == this || v == BASE_HEADER)
 510                 return null;
 511             return (V)v;
 512         }
 513 
 514         /**
 515          * Creates and returns a new SimpleImmutableEntry holding current
 516          * mapping if this node holds a valid value, else null.
 517          * @return new entry or null
 518          */
 519         AbstractMap.SimpleImmutableEntry<K,V> createSnapshot() {
 520             V v = getValidValue();
 521             if (v == null)
 522                 return null;
 523             return new AbstractMap.SimpleImmutableEntry<K,V>(key, v);
 524         }








 525     }
 526 
 527     /* ---------------- Indexing -------------- */
 528 
 529     /**
 530      * Index nodes represent the levels of the skip list.  Note that
 531      * even though both Nodes and Indexes have forward-pointing
 532      * fields, they have different types and are handled in different
 533      * ways, that can't nicely be captured by placing field in a
 534      * shared abstract class.
 535      */
 536     static class Index<K,V> {
 537         final Node<K,V> node;
 538         final Index<K,V> down;
 539         volatile Index<K,V> right;
 540 
 541         /**
 542          * Creates index node with given values.
 543          */
 544         Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
 545             this.node = node;
 546             this.down = down;
 547             this.right = right;
 548         }
 549 
 550         /** Updater for casRight */
 551         static final AtomicReferenceFieldUpdater<Index, Index>
 552             rightUpdater = AtomicReferenceFieldUpdater.newUpdater
 553             (Index.class, Index.class, "right");
 554 
 555         /**
 556          * compareAndSet right field
 557          */
 558         final boolean casRight(Index<K,V> cmp, Index<K,V> val) {
 559             return rightUpdater.compareAndSet(this, cmp, val);
 560         }
 561 
 562         /**
 563          * Returns true if the node this indexes has been deleted.
 564          * @return true if indexed node is known to be deleted
 565          */
 566         final boolean indexesDeletedNode() {
 567             return node.value == null;
 568         }
 569 
 570         /**
 571          * Tries to CAS newSucc as successor.  To minimize races with
 572          * unlink that may lose this index node, if the node being
 573          * indexed is known to be deleted, it doesn't try to link in.
 574          * @param succ the expected current successor
 575          * @param newSucc the new successor
 576          * @return true if successful
 577          */
 578         final boolean link(Index<K,V> succ, Index<K,V> newSucc) {
 579             Node<K,V> n = node;
 580             newSucc.right = succ;
 581             return n.value != null && casRight(succ, newSucc);
 582         }
 583 
 584         /**
 585          * Tries to CAS right field to skip over apparent successor
 586          * succ.  Fails (forcing a retraversal by caller) if this node
 587          * is known to be deleted.
 588          * @param succ the expected current successor
 589          * @return true if successful
 590          */
 591         final boolean unlink(Index<K,V> succ) {
 592             return !indexesDeletedNode() && casRight(succ, succ.right);
 593         }






 594     }
 595 
 596     /* ---------------- Head nodes -------------- */
 597 
 598     /**
 599      * Nodes heading each level keep track of their level.
 600      */
 601     static final class HeadIndex<K,V> extends Index<K,V> {
 602         final int level;
 603         HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {
 604             super(node, down, right);
 605             this.level = level;
 606         }
 607     }
 608 
 609     /* ---------------- Comparison utilities -------------- */
 610 
 611     /**
 612      * Represents a key with a comparator as a Comparable.
 613      *
 614      * Because most sorted collections seem to use natural ordering on
 615      * Comparables (Strings, Integers, etc), most internal methods are
 616      * geared to use them. This is generally faster than checking
 617      * per-comparison whether to use comparator or comparable because
 618      * it doesn't require a (Comparable) cast for each comparison.
 619      * (Optimizers can only sometimes remove such redundant checks
 620      * themselves.) When Comparators are used,
 621      * ComparableUsingComparators are created so that they act in the
 622      * same way as natural orderings. This penalizes use of
 623      * Comparators vs Comparables, which seems like the right
 624      * tradeoff.
 625      */
 626     static final class ComparableUsingComparator<K> implements Comparable<K> {
 627         final K actualKey;
 628         final Comparator<? super K> cmp;
 629         ComparableUsingComparator(K key, Comparator<? super K> cmp) {
 630             this.actualKey = key;
 631             this.cmp = cmp;
 632         }
 633         public int compareTo(K k2) {
 634             return cmp.compare(actualKey, k2);
 635         }
 636     }
 637 
 638     /**
 639      * If using comparator, return a ComparableUsingComparator, else
 640      * cast key as Comparable, which may cause ClassCastException,
 641      * which is propagated back to caller.
 642      */
 643     private Comparable<? super K> comparable(Object key) throws ClassCastException {

 644         if (key == null)
 645             throw new NullPointerException();
 646         if (comparator != null)
 647             return new ComparableUsingComparator<K>((K)key, comparator);
 648         else
 649             return (Comparable<? super K>)key;
 650     }
 651 
 652     /**
 653      * Compares using comparator or natural ordering. Used when the
 654      * ComparableUsingComparator approach doesn't apply.
 655      */
 656     int compare(K k1, K k2) throws ClassCastException {
 657         Comparator<? super K> cmp = comparator;
 658         if (cmp != null)
 659             return cmp.compare(k1, k2);
 660         else
 661             return ((Comparable<? super K>)k1).compareTo(k2);
 662     }
 663 
 664     /**
 665      * Returns true if given key greater than or equal to least and
 666      * strictly less than fence, bypassing either test if least or
 667      * fence are null. Needed mainly in submap operations.
 668      */
 669     boolean inHalfOpenRange(K key, K least, K fence) {
 670         if (key == null)
 671             throw new NullPointerException();
 672         return ((least == null || compare(key, least) >= 0) &&
 673                 (fence == null || compare(key, fence) <  0));
 674     }
 675 
 676     /**
 677      * Returns true if given key greater than or equal to least and less
 678      * or equal to fence. Needed mainly in submap operations.
 679      */
 680     boolean inOpenRange(K key, K least, K fence) {
 681         if (key == null)
 682             throw new NullPointerException();
 683         return ((least == null || compare(key, least) >= 0) &&
 684                 (fence == null || compare(key, fence) <= 0));
 685     }
 686 
 687     /* ---------------- Traversal -------------- */
 688 
 689     /**
 690      * Returns a base-level node with key strictly less than given key,
 691      * or the base-level header if there is no such node.  Also
 692      * unlinks indexes to deleted nodes found along the way.  Callers
 693      * rely on this side-effect of clearing indices to deleted nodes.
 694      * @param key the key
 695      * @return a predecessor of key
 696      */
 697     private Node<K,V> findPredecessor(Comparable<? super K> key) {
 698         if (key == null)
 699             throw new NullPointerException(); // don't postpone errors
 700         for (;;) {
 701             Index<K,V> q = head;
 702             Index<K,V> r = q.right;
 703             for (;;) {
 704                 if (r != null) {
 705                     Node<K,V> n = r.node;
 706                     K k = n.key;
 707                     if (n.value == null) {
 708                         if (!q.unlink(r))
 709                             break;           // restart
 710                         r = q.right;         // reread r
 711                         continue;
 712                     }
 713                     if (key.compareTo(k) > 0) {
 714                         q = r;
 715                         r = r.right;
 716                         continue;
 717                     }
 718                 }
 719                 Index<K,V> d = q.down;
 720                 if (d != null) {
 721                     q = d;
 722                     r = d.right;
 723                 } else
 724                     return q.node;
 725             }
 726         }
 727     }
 728 
 729     /**
 730      * Returns node holding key or null if no such, clearing out any
 731      * deleted nodes seen along the way.  Repeatedly traverses at
 732      * base-level looking for key starting at predecessor returned
 733      * from findPredecessor, processing base-level deletions as
 734      * encountered. Some callers rely on this side-effect of clearing
 735      * deleted nodes.
 736      *
 737      * Restarts occur, at traversal step centered on node n, if:
 738      *
 739      *   (1) After reading n's next field, n is no longer assumed
 740      *       predecessor b's current successor, which means that
 741      *       we don't have a consistent 3-node snapshot and so cannot
 742      *       unlink any subsequent deleted nodes encountered.
 743      *
 744      *   (2) n's value field is null, indicating n is deleted, in
 745      *       which case we help out an ongoing structural deletion
 746      *       before retrying.  Even though there are cases where such
 747      *       unlinking doesn't require restart, they aren't sorted out
 748      *       here because doing so would not usually outweigh cost of
 749      *       restarting.
 750      *
 751      *   (3) n is a marker or n's predecessor's value field is null,
 752      *       indicating (among other possibilities) that
 753      *       findPredecessor returned a deleted node. We can't unlink
 754      *       the node because we don't know its predecessor, so rely
 755      *       on another call to findPredecessor to notice and return
 756      *       some earlier predecessor, which it will do. This check is
 757      *       only strictly needed at beginning of loop, (and the
 758      *       b.value check isn't strictly needed at all) but is done
 759      *       each iteration to help avoid contention with other
 760      *       threads by callers that will fail to be able to change
 761      *       links, and so will retry anyway.
 762      *
 763      * The traversal loops in doPut, doRemove, and findNear all
 764      * include the same three kinds of checks. And specialized
 765      * versions appear in findFirst, and findLast and their
 766      * variants. They can't easily share code because each uses the
 767      * reads of fields held in locals occurring in the orders they
 768      * were performed.
 769      *
 770      * @param key the key
 771      * @return node holding key, or null if no such
 772      */
 773     private Node<K,V> findNode(Comparable<? super K> key) {
 774         for (;;) {
 775             Node<K,V> b = findPredecessor(key);
 776             Node<K,V> n = b.next;
 777             for (;;) {
 778                 if (n == null)
 779                     return null;
 780                 Node<K,V> f = n.next;
 781                 if (n != b.next)                // inconsistent read
 782                     break;
 783                 Object v = n.value;
 784                 if (v == null) {                // n is deleted
 785                     n.helpDelete(b, f);
 786                     break;
 787                 }
 788                 if (v == n || b.value == null)  // b is deleted
 789                     break;
 790                 int c = key.compareTo(n.key);
 791                 if (c == 0)
 792                     return n;
 793                 if (c < 0)
 794                     return null;
 795                 b = n;
 796                 n = f;
 797             }
 798         }
 799     }
 800 
 801     /**
 802      * Specialized variant of findNode to perform Map.get. Does a weak
 803      * traversal, not bothering to fix any deleted index nodes,
 804      * returning early if it happens to see key in index, and passing
 805      * over any deleted base nodes, falling back to getUsingFindNode
 806      * only if it would otherwise return value from an ongoing
 807      * deletion. Also uses "bound" to eliminate need for some
 808      * comparisons (see Pugh Cookbook). Also folds uses of null checks
 809      * and node-skipping because markers have null keys.
 810      * @param okey the key
 811      * @return the value, or null if absent
 812      */
 813     private V doGet(Object okey) {
 814         Comparable<? super K> key = comparable(okey);
 815         Node<K,V> bound = null;
 816         Index<K,V> q = head;
 817         Index<K,V> r = q.right;
 818         Node<K,V> n;
 819         K k;
 820         int c;
 821         for (;;) {
 822             Index<K,V> d;
 823             // Traverse rights
 824             if (r != null && (n = r.node) != bound && (k = n.key) != null) {
 825                 if ((c = key.compareTo(k)) > 0) {
 826                     q = r;
 827                     r = r.right;
 828                     continue;
 829                 } else if (c == 0) {
 830                     Object v = n.value;
 831                     return (v != null)? (V)v : getUsingFindNode(key);
 832                 } else
 833                     bound = n;
 834             }
 835 
 836             // Traverse down
 837             if ((d = q.down) != null) {
 838                 q = d;
 839                 r = d.right;
 840             } else
 841                 break;
 842         }
 843 
 844         // Traverse nexts
 845         for (n = q.node.next;  n != null; n = n.next) {
 846             if ((k = n.key) != null) {
 847                 if ((c = key.compareTo(k)) == 0) {
 848                     Object v = n.value;
 849                     return (v != null)? (V)v : getUsingFindNode(key);
 850                 } else if (c < 0)
 851                     break;
 852             }
 853         }
 854         return null;
 855     }
 856 
 857     /**
 858      * Performs map.get via findNode.  Used as a backup if doGet
 859      * encounters an in-progress deletion.
 860      * @param key the key
 861      * @return the value, or null if absent
 862      */
 863     private V getUsingFindNode(Comparable<? super K> key) {
 864         /*
 865          * Loop needed here and elsewhere in case value field goes
 866          * null just as it is about to be returned, in which case we
 867          * lost a race with a deletion, so must retry.
 868          */
 869         for (;;) {
 870             Node<K,V> n = findNode(key);
 871             if (n == null)
 872                 return null;
 873             Object v = n.value;
 874             if (v != null)
 875                 return (V)v;
 876         }
 877     }
 878 
 879     /* ---------------- Insertion -------------- */
 880 
 881     /**
 882      * Main insertion method.  Adds element if not present, or
 883      * replaces value if present and onlyIfAbsent is false.
 884      * @param kkey the key
 885      * @param value  the value that must be associated with key
 886      * @param onlyIfAbsent if should not insert if already present
 887      * @return the old value, or null if newly inserted
 888      */
 889     private V doPut(K kkey, V value, boolean onlyIfAbsent) {
 890         Comparable<? super K> key = comparable(kkey);
 891         for (;;) {
 892             Node<K,V> b = findPredecessor(key);
 893             Node<K,V> n = b.next;
 894             for (;;) {
 895                 if (n != null) {
 896                     Node<K,V> f = n.next;
 897                     if (n != b.next)               // inconsistent read
 898                         break;
 899                     Object v = n.value;
 900                     if (v == null) {               // n is deleted
 901                         n.helpDelete(b, f);
 902                         break;
 903                     }
 904                     if (v == n || b.value == null) // b is deleted
 905                         break;
 906                     int c = key.compareTo(n.key);
 907                     if (c > 0) {
 908                         b = n;
 909                         n = f;
 910                         continue;
 911                     }
 912                     if (c == 0) {
 913                         if (onlyIfAbsent || n.casValue(v, value))
 914                             return (V)v;
 915                         else
 916                             break; // restart if lost race to replace value
 917                     }
 918                     // else c < 0; fall through
 919                 }
 920 
 921                 Node<K,V> z = new Node<K,V>(kkey, value, n);
 922                 if (!b.casNext(n, z))
 923                     break;         // restart if lost race to append to b
 924                 int level = randomLevel();
 925                 if (level > 0)
 926                     insertIndex(z, level);
 927                 return null;
 928             }
 929         }
 930     }
 931 
 932     /**
 933      * Returns a random level for inserting a new node.
 934      * Hardwired to k=1, p=0.5, max 31 (see above and
 935      * Pugh's "Skip List Cookbook", sec 3.4).
 936      *
 937      * This uses the simplest of the generators described in George
 938      * Marsaglia's "Xorshift RNGs" paper.  This is not a high-quality
 939      * generator but is acceptable here.
 940      */
 941     private int randomLevel() {
 942         int x = randomSeed;
 943         x ^= x << 13;
 944         x ^= x >>> 17;
 945         randomSeed = x ^= x << 5;
 946         if ((x & 0x8001) != 0) // test highest and lowest bits
 947             return 0;
 948         int level = 1;
 949         while (((x >>>= 1) & 1) != 0) ++level;
 950         return level;
 951     }
 952 
 953     /**
 954      * Creates and adds index nodes for the given node.
 955      * @param z the node
 956      * @param level the level of the index
 957      */
 958     private void insertIndex(Node<K,V> z, int level) {
 959         HeadIndex<K,V> h = head;
 960         int max = h.level;
 961 
 962         if (level <= max) {
 963             Index<K,V> idx = null;
 964             for (int i = 1; i <= level; ++i)
 965                 idx = new Index<K,V>(z, idx, null);
 966             addIndex(idx, h, level);
 967 
 968         } else { // Add a new level
 969             /*
 970              * To reduce interference by other threads checking for
 971              * empty levels in tryReduceLevel, new levels are added
 972              * with initialized right pointers. Which in turn requires
 973              * keeping levels in an array to access them while
 974              * creating new head index nodes from the opposite
 975              * direction.
 976              */
 977             level = max + 1;
 978             Index<K,V>[] idxs = (Index<K,V>[])new Index[level+1];
 979             Index<K,V> idx = null;
 980             for (int i = 1; i <= level; ++i)
 981                 idxs[i] = idx = new Index<K,V>(z, idx, null);
 982 
 983             HeadIndex<K,V> oldh;
 984             int k;
 985             for (;;) {
 986                 oldh = head;
 987                 int oldLevel = oldh.level;
 988                 if (level <= oldLevel) { // lost race to add level
 989                     k = level;
 990                     break;
 991                 }
 992                 HeadIndex<K,V> newh = oldh;
 993                 Node<K,V> oldbase = oldh.node;
 994                 for (int j = oldLevel+1; j <= level; ++j)
 995                     newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);
 996                 if (casHead(oldh, newh)) {
 997                     k = oldLevel;
 998                     break;
 999                 }
1000             }
1001             addIndex(idxs[k], oldh, k);
1002         }
1003     }
1004 
1005     /**
1006      * Adds given index nodes from given level down to 1.
1007      * @param idx the topmost index node being inserted
1008      * @param h the value of head to use to insert. This must be
1009      * snapshotted by callers to provide correct insertion level
1010      * @param indexLevel the level of the index
1011      */
1012     private void addIndex(Index<K,V> idx, HeadIndex<K,V> h, int indexLevel) {
1013         // Track next level to insert in case of retries
1014         int insertionLevel = indexLevel;
1015         Comparable<? super K> key = comparable(idx.node.key);
1016         if (key == null) throw new NullPointerException();
1017 
1018         // Similar to findPredecessor, but adding index nodes along
1019         // path to key.
1020         for (;;) {
1021             int j = h.level;
1022             Index<K,V> q = h;
1023             Index<K,V> r = q.right;
1024             Index<K,V> t = idx;
1025             for (;;) {
1026                 if (r != null) {
1027                     Node<K,V> n = r.node;
1028                     // compare before deletion check avoids needing recheck
1029                     int c = key.compareTo(n.key);
1030                     if (n.value == null) {
1031                         if (!q.unlink(r))
1032                             break;
1033                         r = q.right;
1034                         continue;
1035                     }
1036                     if (c > 0) {
1037                         q = r;
1038                         r = r.right;
1039                         continue;
1040                     }
1041                 }
1042 
1043                 if (j == insertionLevel) {
1044                     // Don't insert index if node already deleted
1045                     if (t.indexesDeletedNode()) {
1046                         findNode(key); // cleans up
1047                         return;
1048                     }
1049                     if (!q.link(r, t))
1050                         break; // restart
1051                     if (--insertionLevel == 0) {
1052                         // need final deletion check before return
1053                         if (t.indexesDeletedNode())
1054                             findNode(key);
1055                         return;
1056                     }
1057                 }
1058 
1059                 if (--j >= insertionLevel && j < indexLevel)
1060                     t = t.down;
1061                 q = q.down;
1062                 r = q.right;
1063             }
1064         }
1065     }
1066 
1067     /* ---------------- Deletion -------------- */
1068 
1069     /**
1070      * Main deletion method. Locates node, nulls value, appends a
1071      * deletion marker, unlinks predecessor, removes associated index
1072      * nodes, and possibly reduces head index level.
1073      *
1074      * Index nodes are cleared out simply by calling findPredecessor.
1075      * which unlinks indexes to deleted nodes found along path to key,
1076      * which will include the indexes to this node.  This is done
1077      * unconditionally. We can't check beforehand whether there are
1078      * index nodes because it might be the case that some or all
1079      * indexes hadn't been inserted yet for this node during initial
1080      * search for it, and we'd like to ensure lack of garbage
1081      * retention, so must call to be sure.
1082      *
1083      * @param okey the key
1084      * @param value if non-null, the value that must be
1085      * associated with key
1086      * @return the node, or null if not found
1087      */
1088     final V doRemove(Object okey, Object value) {
1089         Comparable<? super K> key = comparable(okey);
1090         for (;;) {
1091             Node<K,V> b = findPredecessor(key);
1092             Node<K,V> n = b.next;
1093             for (;;) {
1094                 if (n == null)
1095                     return null;
1096                 Node<K,V> f = n.next;
1097                 if (n != b.next)                    // inconsistent read
1098                     break;
1099                 Object v = n.value;
1100                 if (v == null) {                    // n is deleted
1101                     n.helpDelete(b, f);
1102                     break;
1103                 }
1104                 if (v == n || b.value == null)      // b is deleted
1105                     break;
1106                 int c = key.compareTo(n.key);
1107                 if (c < 0)
1108                     return null;
1109                 if (c > 0) {
1110                     b = n;
1111                     n = f;
1112                     continue;
1113                 }
1114                 if (value != null && !value.equals(v))
1115                     return null;
1116                 if (!n.casValue(v, null))
1117                     break;
1118                 if (!n.appendMarker(f) || !b.casNext(n, f))
1119                     findNode(key);                  // Retry via findNode
1120                 else {
1121                     findPredecessor(key);           // Clean index
1122                     if (head.right == null)
1123                         tryReduceLevel();
1124                 }
1125                 return (V)v;
1126             }
1127         }
1128     }
1129 
1130     /**
1131      * Possibly reduce head level if it has no nodes.  This method can
1132      * (rarely) make mistakes, in which case levels can disappear even
1133      * though they are about to contain index nodes. This impacts
1134      * performance, not correctness.  To minimize mistakes as well as
1135      * to reduce hysteresis, the level is reduced by one only if the
1136      * topmost three levels look empty. Also, if the removed level
1137      * looks non-empty after CAS, we try to change it back quick
1138      * before anyone notices our mistake! (This trick works pretty
1139      * well because this method will practically never make mistakes
1140      * unless current thread stalls immediately before first CAS, in
1141      * which case it is very unlikely to stall again immediately
1142      * afterwards, so will recover.)
1143      *
1144      * We put up with all this rather than just let levels grow
1145      * because otherwise, even a small map that has undergone a large
1146      * number of insertions and removals will have a lot of levels,
1147      * slowing down access more than would an occasional unwanted
1148      * reduction.
1149      */
1150     private void tryReduceLevel() {
1151         HeadIndex<K,V> h = head;
1152         HeadIndex<K,V> d;
1153         HeadIndex<K,V> e;
1154         if (h.level > 3 &&
1155             (d = (HeadIndex<K,V>)h.down) != null &&
1156             (e = (HeadIndex<K,V>)d.down) != null &&
1157             e.right == null &&
1158             d.right == null &&
1159             h.right == null &&
1160             casHead(h, d) && // try to set
1161             h.right != null) // recheck
1162             casHead(d, h);   // try to backout
1163     }
1164 
1165     /* ---------------- Finding and removing first element -------------- */
1166 
1167     /**
1168      * Specialized variant of findNode to get first valid node.
1169      * @return first node or null if empty
1170      */
1171     Node<K,V> findFirst() {
1172         for (;;) {
1173             Node<K,V> b = head.node;
1174             Node<K,V> n = b.next;
1175             if (n == null)
1176                 return null;
1177             if (n.value != null)
1178                 return n;
1179             n.helpDelete(b, n.next);
1180         }
1181     }
1182 
1183     /**
1184      * Removes first entry; returns its snapshot.
1185      * @return null if empty, else snapshot of first entry
1186      */
1187     Map.Entry<K,V> doRemoveFirstEntry() {
1188         for (;;) {
1189             Node<K,V> b = head.node;
1190             Node<K,V> n = b.next;
1191             if (n == null)
1192                 return null;
1193             Node<K,V> f = n.next;
1194             if (n != b.next)
1195                 continue;
1196             Object v = n.value;
1197             if (v == null) {
1198                 n.helpDelete(b, f);
1199                 continue;
1200             }
1201             if (!n.casValue(v, null))
1202                 continue;
1203             if (!n.appendMarker(f) || !b.casNext(n, f))
1204                 findFirst(); // retry
1205             clearIndexToFirst();
1206             return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, (V)v);
1207         }
1208     }
1209 
1210     /**
1211      * Clears out index nodes associated with deleted first entry.
1212      */
1213     private void clearIndexToFirst() {
1214         for (;;) {
1215             Index<K,V> q = head;
1216             for (;;) {
1217                 Index<K,V> r = q.right;
1218                 if (r != null && r.indexesDeletedNode() && !q.unlink(r))
1219                     break;
1220                 if ((q = q.down) == null) {
1221                     if (head.right == null)
1222                         tryReduceLevel();
1223                     return;
1224                 }
1225             }
1226         }
1227     }
1228 
1229 
1230     /* ---------------- Finding and removing last element -------------- */
1231 
1232     /**
1233      * Specialized version of find to get last valid node.
1234      * @return last node or null if empty
1235      */
1236     Node<K,V> findLast() {
1237         /*
1238          * findPredecessor can't be used to traverse index level
1239          * because this doesn't use comparisons.  So traversals of
1240          * both levels are folded together.
1241          */
1242         Index<K,V> q = head;
1243         for (;;) {
1244             Index<K,V> d, r;
1245             if ((r = q.right) != null) {
1246                 if (r.indexesDeletedNode()) {
1247                     q.unlink(r);
1248                     q = head; // restart
1249                 }
1250                 else
1251                     q = r;
1252             } else if ((d = q.down) != null) {
1253                 q = d;
1254             } else {
1255                 Node<K,V> b = q.node;
1256                 Node<K,V> n = b.next;
1257                 for (;;) {
1258                     if (n == null)
1259                         return (b.isBaseHeader())? null : b;
1260                     Node<K,V> f = n.next;            // inconsistent read
1261                     if (n != b.next)
1262                         break;
1263                     Object v = n.value;
1264                     if (v == null) {                 // n is deleted
1265                         n.helpDelete(b, f);
1266                         break;
1267                     }
1268                     if (v == n || b.value == null)   // b is deleted
1269                         break;
1270                     b = n;
1271                     n = f;
1272                 }
1273                 q = head; // restart
1274             }
1275         }
1276     }
1277 
1278     /**
1279      * Specialized variant of findPredecessor to get predecessor of last
1280      * valid node.  Needed when removing the last entry.  It is possible
1281      * that all successors of returned node will have been deleted upon
1282      * return, in which case this method can be retried.
1283      * @return likely predecessor of last node
1284      */
1285     private Node<K,V> findPredecessorOfLast() {
1286         for (;;) {
1287             Index<K,V> q = head;
1288             for (;;) {
1289                 Index<K,V> d, r;
1290                 if ((r = q.right) != null) {
1291                     if (r.indexesDeletedNode()) {
1292                         q.unlink(r);
1293                         break;    // must restart
1294                     }
1295                     // proceed as far across as possible without overshooting
1296                     if (r.node.next != null) {
1297                         q = r;
1298                         continue;
1299                     }
1300                 }
1301                 if ((d = q.down) != null)
1302                     q = d;
1303                 else
1304                     return q.node;
1305             }
1306         }
1307     }
1308 
1309     /**
1310      * Removes last entry; returns its snapshot.
1311      * Specialized variant of doRemove.
1312      * @return null if empty, else snapshot of last entry
1313      */
1314     Map.Entry<K,V> doRemoveLastEntry() {
1315         for (;;) {
1316             Node<K,V> b = findPredecessorOfLast();
1317             Node<K,V> n = b.next;
1318             if (n == null) {
1319                 if (b.isBaseHeader())               // empty
1320                     return null;
1321                 else
1322                     continue; // all b's successors are deleted; retry
1323             }
1324             for (;;) {
1325                 Node<K,V> f = n.next;
1326                 if (n != b.next)                    // inconsistent read
1327                     break;
1328                 Object v = n.value;
1329                 if (v == null) {                    // n is deleted
1330                     n.helpDelete(b, f);
1331                     break;
1332                 }
1333                 if (v == n || b.value == null)      // b is deleted
1334                     break;
1335                 if (f != null) {
1336                     b = n;
1337                     n = f;
1338                     continue;
1339                 }
1340                 if (!n.casValue(v, null))
1341                     break;
1342                 K key = n.key;
1343                 Comparable<? super K> ck = comparable(key);
1344                 if (!n.appendMarker(f) || !b.casNext(n, f))
1345                     findNode(ck);                  // Retry via findNode
1346                 else {
1347                     findPredecessor(ck);           // Clean index
1348                     if (head.right == null)
1349                         tryReduceLevel();
1350                 }
1351                 return new AbstractMap.SimpleImmutableEntry<K,V>(key, (V)v);
1352             }
1353         }
1354     }
1355 
1356     /* ---------------- Relational operations -------------- */
1357 
1358     // Control values OR'ed as arguments to findNear
1359 
1360     private static final int EQ = 1;
1361     private static final int LT = 2;
1362     private static final int GT = 0; // Actually checked as !LT
1363 
1364     /**
1365      * Utility for ceiling, floor, lower, higher methods.
1366      * @param kkey the key
1367      * @param rel the relation -- OR'ed combination of EQ, LT, GT
1368      * @return nearest node fitting relation, or null if no such
1369      */
1370     Node<K,V> findNear(K kkey, int rel) {
1371         Comparable<? super K> key = comparable(kkey);
1372         for (;;) {
1373             Node<K,V> b = findPredecessor(key);
1374             Node<K,V> n = b.next;
1375             for (;;) {
1376                 if (n == null)
1377                     return ((rel & LT) == 0 || b.isBaseHeader())? null : b;
1378                 Node<K,V> f = n.next;
1379                 if (n != b.next)                  // inconsistent read
1380                     break;
1381                 Object v = n.value;
1382                 if (v == null) {                  // n is deleted
1383                     n.helpDelete(b, f);
1384                     break;
1385                 }
1386                 if (v == n || b.value == null)    // b is deleted
1387                     break;
1388                 int c = key.compareTo(n.key);
1389                 if ((c == 0 && (rel & EQ) != 0) ||
1390                     (c <  0 && (rel & LT) == 0))
1391                     return n;
1392                 if ( c <= 0 && (rel & LT) != 0)
1393                     return (b.isBaseHeader())? null : b;
1394                 b = n;
1395                 n = f;
1396             }
1397         }
1398     }
1399 
1400     /**
1401      * Returns SimpleImmutableEntry for results of findNear.
1402      * @param key the key
1403      * @param rel the relation -- OR'ed combination of EQ, LT, GT
1404      * @return Entry fitting relation, or null if no such
1405      */
1406     AbstractMap.SimpleImmutableEntry<K,V> getNear(K key, int rel) {
1407         for (;;) {
1408             Node<K,V> n = findNear(key, rel);
1409             if (n == null)
1410                 return null;
1411             AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
1412             if (e != null)
1413                 return e;
1414         }
1415     }
1416 
1417 
1418     /* ---------------- Constructors -------------- */
1419 
1420     /**
1421      * Constructs a new, empty map, sorted according to the
1422      * {@linkplain Comparable natural ordering} of the keys.
1423      */
1424     public ConcurrentSkipListMap() {
1425         this.comparator = null;
1426         initialize();
1427     }
1428 
1429     /**
1430      * Constructs a new, empty map, sorted according to the specified
1431      * comparator.
1432      *
1433      * @param comparator the comparator that will be used to order this map.
1434      *        If <tt>null</tt>, the {@linkplain Comparable natural
1435      *        ordering} of the keys will be used.
1436      */
1437     public ConcurrentSkipListMap(Comparator<? super K> comparator) {
1438         this.comparator = comparator;
1439         initialize();
1440     }
1441 
1442     /**
1443      * Constructs a new map containing the same mappings as the given map,
1444      * sorted according to the {@linkplain Comparable natural ordering} of
1445      * the keys.
1446      *
1447      * @param  m the map whose mappings are to be placed in this map
1448      * @throws ClassCastException if the keys in <tt>m</tt> are not
1449      *         {@link Comparable}, or are not mutually comparable
1450      * @throws NullPointerException if the specified map or any of its keys
1451      *         or values are null
1452      */
1453     public ConcurrentSkipListMap(Map<? extends K, ? extends V> m) {
1454         this.comparator = null;
1455         initialize();
1456         putAll(m);
1457     }
1458 
1459     /**
1460      * Constructs a new map containing the same mappings and using the
1461      * same ordering as the specified sorted map.
1462      *
1463      * @param m the sorted map whose mappings are to be placed in this
1464      *        map, and whose comparator is to be used to sort this map
1465      * @throws NullPointerException if the specified sorted map or any of
1466      *         its keys or values are null
1467      */
1468     public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) {
1469         this.comparator = m.comparator();
1470         initialize();
1471         buildFromSorted(m);
1472     }
1473 
1474     /**
1475      * Returns a shallow copy of this <tt>ConcurrentSkipListMap</tt>
1476      * instance. (The keys and values themselves are not cloned.)
1477      *
1478      * @return a shallow copy of this map
1479      */
1480     public ConcurrentSkipListMap<K,V> clone() {
1481         ConcurrentSkipListMap<K,V> clone = null;
1482         try {
1483             clone = (ConcurrentSkipListMap<K,V>) super.clone();
1484         } catch (CloneNotSupportedException e) {
1485             throw new InternalError();
1486         }
1487 
1488         clone.initialize();
1489         clone.buildFromSorted(this);
1490         return clone;
1491     }
1492 
1493     /**
1494      * Streamlined bulk insertion to initialize from elements of
1495      * given sorted map.  Call only from constructor or clone
1496      * method.
1497      */
1498     private void buildFromSorted(SortedMap<K, ? extends V> map) {
1499         if (map == null)
1500             throw new NullPointerException();
1501 
1502         HeadIndex<K,V> h = head;
1503         Node<K,V> basepred = h.node;
1504 
1505         // Track the current rightmost node at each level. Uses an
1506         // ArrayList to avoid committing to initial or maximum level.
1507         ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>();
1508 
1509         // initialize
1510         for (int i = 0; i <= h.level; ++i)
1511             preds.add(null);
1512         Index<K,V> q = h;
1513         for (int i = h.level; i > 0; --i) {
1514             preds.set(i, q);
1515             q = q.down;
1516         }
1517 
1518         Iterator<? extends Map.Entry<? extends K, ? extends V>> it =
1519             map.entrySet().iterator();
1520         while (it.hasNext()) {
1521             Map.Entry<? extends K, ? extends V> e = it.next();
1522             int j = randomLevel();
1523             if (j > h.level) j = h.level + 1;
1524             K k = e.getKey();
1525             V v = e.getValue();
1526             if (k == null || v == null)
1527                 throw new NullPointerException();
1528             Node<K,V> z = new Node<K,V>(k, v, null);
1529             basepred.next = z;
1530             basepred = z;
1531             if (j > 0) {
1532                 Index<K,V> idx = null;
1533                 for (int i = 1; i <= j; ++i) {
1534                     idx = new Index<K,V>(z, idx, null);
1535                     if (i > h.level)
1536                         h = new HeadIndex<K,V>(h.node, h, idx, i);
1537 
1538                     if (i < preds.size()) {
1539                         preds.get(i).right = idx;
1540                         preds.set(i, idx);
1541                     } else
1542                         preds.add(idx);
1543                 }
1544             }
1545         }
1546         head = h;
1547     }
1548 
1549     /* ---------------- Serialization -------------- */
1550 
1551     /**
1552      * Save the state of this map to a stream.
1553      *
1554      * @serialData The key (Object) and value (Object) for each
1555      * key-value mapping represented by the map, followed by
1556      * <tt>null</tt>. The key-value mappings are emitted in key-order
1557      * (as determined by the Comparator, or by the keys' natural
1558      * ordering if no Comparator).
1559      */
1560     private void writeObject(java.io.ObjectOutputStream s)
1561         throws java.io.IOException {
1562         // Write out the Comparator and any hidden stuff
1563         s.defaultWriteObject();
1564 
1565         // Write out keys and values (alternating)
1566         for (Node<K,V> n = findFirst(); n != null; n = n.next) {
1567             V v = n.getValidValue();
1568             if (v != null) {
1569                 s.writeObject(n.key);
1570                 s.writeObject(v);
1571             }
1572         }
1573         s.writeObject(null);
1574     }
1575 
1576     /**
1577      * Reconstitute the map from a stream.
1578      */
1579     private void readObject(final java.io.ObjectInputStream s)
1580         throws java.io.IOException, ClassNotFoundException {
1581         // Read in the Comparator and any hidden stuff
1582         s.defaultReadObject();
1583         // Reset transients
1584         initialize();
1585 
1586         /*
1587          * This is nearly identical to buildFromSorted, but is
1588          * distinct because readObject calls can't be nicely adapted
1589          * as the kind of iterator needed by buildFromSorted. (They
1590          * can be, but doing so requires type cheats and/or creation
1591          * of adaptor classes.) It is simpler to just adapt the code.
1592          */
1593 
1594         HeadIndex<K,V> h = head;
1595         Node<K,V> basepred = h.node;
1596         ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>();
1597         for (int i = 0; i <= h.level; ++i)
1598             preds.add(null);
1599         Index<K,V> q = h;
1600         for (int i = h.level; i > 0; --i) {
1601             preds.set(i, q);
1602             q = q.down;
1603         }
1604 
1605         for (;;) {
1606             Object k = s.readObject();
1607             if (k == null)
1608                 break;
1609             Object v = s.readObject();
1610             if (v == null)
1611                 throw new NullPointerException();
1612             K key = (K) k;
1613             V val = (V) v;
1614             int j = randomLevel();
1615             if (j > h.level) j = h.level + 1;
1616             Node<K,V> z = new Node<K,V>(key, val, null);
1617             basepred.next = z;
1618             basepred = z;
1619             if (j > 0) {
1620                 Index<K,V> idx = null;
1621                 for (int i = 1; i <= j; ++i) {
1622                     idx = new Index<K,V>(z, idx, null);
1623                     if (i > h.level)
1624                         h = new HeadIndex<K,V>(h.node, h, idx, i);
1625 
1626                     if (i < preds.size()) {
1627                         preds.get(i).right = idx;
1628                         preds.set(i, idx);
1629                     } else
1630                         preds.add(idx);
1631                 }
1632             }
1633         }
1634         head = h;
1635     }
1636 
1637     /* ------ Map API methods ------ */
1638 
1639     /**
1640      * Returns <tt>true</tt> if this map contains a mapping for the specified
1641      * key.
1642      *
1643      * @param key key whose presence in this map is to be tested
1644      * @return <tt>true</tt> if this map contains a mapping for the specified key
1645      * @throws ClassCastException if the specified key cannot be compared
1646      *         with the keys currently in the map
1647      * @throws NullPointerException if the specified key is null
1648      */
1649     public boolean containsKey(Object key) {
1650         return doGet(key) != null;
1651     }
1652 
1653     /**
1654      * Returns the value to which the specified key is mapped,
1655      * or {@code null} if this map contains no mapping for the key.
1656      *
1657      * <p>More formally, if this map contains a mapping from a key
1658      * {@code k} to a value {@code v} such that {@code key} compares
1659      * equal to {@code k} according to the map's ordering, then this
1660      * method returns {@code v}; otherwise it returns {@code null}.
1661      * (There can be at most one such mapping.)
1662      *
1663      * @throws ClassCastException if the specified key cannot be compared
1664      *         with the keys currently in the map
1665      * @throws NullPointerException if the specified key is null
1666      */
1667     public V get(Object key) {
1668         return doGet(key);
1669     }
1670 
1671     /**
1672      * Associates the specified value with the specified key in this map.
1673      * If the map previously contained a mapping for the key, the old
1674      * value is replaced.
1675      *
1676      * @param key key with which the specified value is to be associated
1677      * @param value value to be associated with the specified key
1678      * @return the previous value associated with the specified key, or
1679      *         <tt>null</tt> if there was no mapping for the key
1680      * @throws ClassCastException if the specified key cannot be compared
1681      *         with the keys currently in the map
1682      * @throws NullPointerException if the specified key or value is null
1683      */
1684     public V put(K key, V value) {
1685         if (value == null)
1686             throw new NullPointerException();
1687         return doPut(key, value, false);
1688     }
1689 
1690     /**
1691      * Removes the mapping for the specified key from this map if present.
1692      *
1693      * @param  key key for which mapping should be removed
1694      * @return the previous value associated with the specified key, or
1695      *         <tt>null</tt> if there was no mapping for the key
1696      * @throws ClassCastException if the specified key cannot be compared
1697      *         with the keys currently in the map
1698      * @throws NullPointerException if the specified key is null
1699      */
1700     public V remove(Object key) {
1701         return doRemove(key, null);
1702     }
1703 
1704     /**
1705      * Returns <tt>true</tt> if this map maps one or more keys to the
1706      * specified value.  This operation requires time linear in the
1707      * map size.
1708      *
1709      * @param value value whose presence in this map is to be tested
1710      * @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
1711      *         <tt>false</tt> otherwise
1712      * @throws NullPointerException if the specified value is null
1713      */
1714     public boolean containsValue(Object value) {
1715         if (value == null)
1716             throw new NullPointerException();
1717         for (Node<K,V> n = findFirst(); n != null; n = n.next) {
1718             V v = n.getValidValue();
1719             if (v != null && value.equals(v))
1720                 return true;
1721         }
1722         return false;
1723     }
1724 
1725     /**
1726      * Returns the number of key-value mappings in this map.  If this map
1727      * contains more than <tt>Integer.MAX_VALUE</tt> elements, it
1728      * returns <tt>Integer.MAX_VALUE</tt>.
1729      *
1730      * <p>Beware that, unlike in most collections, this method is
1731      * <em>NOT</em> a constant-time operation. Because of the
1732      * asynchronous nature of these maps, determining the current
1733      * number of elements requires traversing them all to count them.
1734      * Additionally, it is possible for the size to change during
1735      * execution of this method, in which case the returned result
1736      * will be inaccurate. Thus, this method is typically not very
1737      * useful in concurrent applications.
1738      *
1739      * @return the number of elements in this map
1740      */
1741     public int size() {
1742         long count = 0;
1743         for (Node<K,V> n = findFirst(); n != null; n = n.next) {
1744             if (n.getValidValue() != null)
1745                 ++count;
1746         }
1747         return (count >= Integer.MAX_VALUE)? Integer.MAX_VALUE : (int)count;
1748     }
1749 
1750     /**
1751      * Returns <tt>true</tt> if this map contains no key-value mappings.
1752      * @return <tt>true</tt> if this map contains no key-value mappings
1753      */
1754     public boolean isEmpty() {
1755         return findFirst() == null;
1756     }
1757 
1758     /**
1759      * Removes all of the mappings from this map.
1760      */
1761     public void clear() {
1762         initialize();
1763     }
1764 
1765     /* ---------------- View methods -------------- */
1766 
1767     /*
1768      * Note: Lazy initialization works for views because view classes
1769      * are stateless/immutable so it doesn't matter wrt correctness if
1770      * more than one is created (which will only rarely happen).  Even
1771      * so, the following idiom conservatively ensures that the method
1772      * returns the one it created if it does so, not one created by
1773      * another racing thread.
1774      */
1775 
1776     /**
1777      * Returns a {@link NavigableSet} view of the keys contained in this map.
1778      * The set's iterator returns the keys in ascending order.
1779      * The set is backed by the map, so changes to the map are
1780      * reflected in the set, and vice-versa.  The set supports element
1781      * removal, which removes the corresponding mapping from the map,
1782      * via the {@code Iterator.remove}, {@code Set.remove},
1783      * {@code removeAll}, {@code retainAll}, and {@code clear}
1784      * operations.  It does not support the {@code add} or {@code addAll}
1785      * operations.
1786      *
1787      * <p>The view's {@code iterator} is a "weakly consistent" iterator
1788      * that will never throw {@link ConcurrentModificationException},
1789      * and guarantees to traverse elements as they existed upon
1790      * construction of the iterator, and may (but is not guaranteed to)
1791      * reflect any modifications subsequent to construction.
1792      *
1793      * <p>This method is equivalent to method {@code navigableKeySet}.
1794      *
1795      * @return a navigable set view of the keys in this map
1796      */
1797      public NavigableSet<K> keySet() {
1798         KeySet ks = keySet;
1799         return (ks != null) ? ks : (keySet = new KeySet(this));
1800     }
1801 
1802     public NavigableSet<K> navigableKeySet() {
1803         KeySet ks = keySet;
1804         return (ks != null) ? ks : (keySet = new KeySet(this));
1805     }
1806 
1807     /**
1808      * Returns a {@link Collection} view of the values contained in this map.
1809      * The collection's iterator returns the values in ascending order
1810      * of the corresponding keys.
1811      * The collection is backed by the map, so changes to the map are
1812      * reflected in the collection, and vice-versa.  The collection
1813      * supports element removal, which removes the corresponding
1814      * mapping from the map, via the <tt>Iterator.remove</tt>,
1815      * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1816      * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
1817      * support the <tt>add</tt> or <tt>addAll</tt> operations.
1818      *
1819      * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1820      * that will never throw {@link ConcurrentModificationException},
1821      * and guarantees to traverse elements as they existed upon
1822      * construction of the iterator, and may (but is not guaranteed to)
1823      * reflect any modifications subsequent to construction.
1824      */
1825     public Collection<V> values() {
1826         Values vs = values;
1827         return (vs != null) ? vs : (values = new Values(this));
1828     }
1829 
1830     /**
1831      * Returns a {@link Set} view of the mappings contained in this map.
1832      * The set's iterator returns the entries in ascending key order.
1833      * The set is backed by the map, so changes to the map are
1834      * reflected in the set, and vice-versa.  The set supports element
1835      * removal, which removes the corresponding mapping from the map,
1836      * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1837      * <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
1838      * operations.  It does not support the <tt>add</tt> or
1839      * <tt>addAll</tt> operations.
1840      *
1841      * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1842      * that will never throw {@link ConcurrentModificationException},
1843      * and guarantees to traverse elements as they existed upon
1844      * construction of the iterator, and may (but is not guaranteed to)
1845      * reflect any modifications subsequent to construction.
1846      *
1847      * <p>The <tt>Map.Entry</tt> elements returned by
1848      * <tt>iterator.next()</tt> do <em>not</em> support the
1849      * <tt>setValue</tt> operation.
1850      *
1851      * @return a set view of the mappings contained in this map,
1852      *         sorted in ascending key order
1853      */
1854     public Set<Map.Entry<K,V>> entrySet() {
1855         EntrySet es = entrySet;
1856         return (es != null) ? es : (entrySet = new EntrySet(this));
1857     }
1858 
1859     public ConcurrentNavigableMap<K,V> descendingMap() {
1860         ConcurrentNavigableMap<K,V> dm = descendingMap;
1861         return (dm != null) ? dm : (descendingMap = new SubMap<K,V>
1862                                     (this, null, false, null, false, true));
1863     }
1864 
1865     public NavigableSet<K> descendingKeySet() {
1866         return descendingMap().navigableKeySet();
1867     }
1868 
1869     /* ---------------- AbstractMap Overrides -------------- */
1870 
1871     /**
1872      * Compares the specified object with this map for equality.
1873      * Returns <tt>true</tt> if the given object is also a map and the
1874      * two maps represent the same mappings.  More formally, two maps
1875      * <tt>m1</tt> and <tt>m2</tt> represent the same mappings if
1876      * <tt>m1.entrySet().equals(m2.entrySet())</tt>.  This
1877      * operation may return misleading results if either map is
1878      * concurrently modified during execution of this method.
1879      *
1880      * @param o object to be compared for equality with this map
1881      * @return <tt>true</tt> if the specified object is equal to this map
1882      */
1883     public boolean equals(Object o) {
1884         if (o == this)
1885             return true;
1886         if (!(o instanceof Map))
1887             return false;
1888         Map<?,?> m = (Map<?,?>) o;
1889         try {
1890             for (Map.Entry<K,V> e : this.entrySet())
1891                 if (! e.getValue().equals(m.get(e.getKey())))
1892                     return false;
1893             for (Map.Entry<?,?> e : m.entrySet()) {
1894                 Object k = e.getKey();
1895                 Object v = e.getValue();
1896                 if (k == null || v == null || !v.equals(get(k)))
1897                     return false;
1898             }
1899             return true;
1900         } catch (ClassCastException unused) {
1901             return false;
1902         } catch (NullPointerException unused) {
1903             return false;
1904         }
1905     }
1906 
1907     /* ------ ConcurrentMap API methods ------ */
1908 
1909     /**
1910      * {@inheritDoc}
1911      *
1912      * @return the previous value associated with the specified key,
1913      *         or <tt>null</tt> if there was no mapping for the key
1914      * @throws ClassCastException if the specified key cannot be compared
1915      *         with the keys currently in the map
1916      * @throws NullPointerException if the specified key or value is null
1917      */
1918     public V putIfAbsent(K key, V value) {
1919         if (value == null)
1920             throw new NullPointerException();
1921         return doPut(key, value, true);
1922     }
1923 
1924     /**
1925      * {@inheritDoc}
1926      *
1927      * @throws ClassCastException if the specified key cannot be compared
1928      *         with the keys currently in the map
1929      * @throws NullPointerException if the specified key is null
1930      */
1931     public boolean remove(Object key, Object value) {
1932         if (key == null)
1933             throw new NullPointerException();
1934         if (value == null)
1935             return false;
1936         return doRemove(key, value) != null;
1937     }
1938 
1939     /**
1940      * {@inheritDoc}
1941      *
1942      * @throws ClassCastException if the specified key cannot be compared
1943      *         with the keys currently in the map
1944      * @throws NullPointerException if any of the arguments are null
1945      */
1946     public boolean replace(K key, V oldValue, V newValue) {
1947         if (oldValue == null || newValue == null)
1948             throw new NullPointerException();
1949         Comparable<? super K> k = comparable(key);
1950         for (;;) {
1951             Node<K,V> n = findNode(k);
1952             if (n == null)
1953                 return false;
1954             Object v = n.value;
1955             if (v != null) {
1956                 if (!oldValue.equals(v))
1957                     return false;
1958                 if (n.casValue(v, newValue))
1959                     return true;
1960             }
1961         }
1962     }
1963 
1964     /**
1965      * {@inheritDoc}
1966      *
1967      * @return the previous value associated with the specified key,
1968      *         or <tt>null</tt> if there was no mapping for the key
1969      * @throws ClassCastException if the specified key cannot be compared
1970      *         with the keys currently in the map
1971      * @throws NullPointerException if the specified key or value is null
1972      */
1973     public V replace(K key, V value) {
1974         if (value == null)
1975             throw new NullPointerException();
1976         Comparable<? super K> k = comparable(key);
1977         for (;;) {
1978             Node<K,V> n = findNode(k);
1979             if (n == null)
1980                 return null;
1981             Object v = n.value;
1982             if (v != null && n.casValue(v, value))
1983                 return (V)v;
1984         }
1985     }
1986 
1987     /* ------ SortedMap API methods ------ */
1988 
1989     public Comparator<? super K> comparator() {
1990         return comparator;
1991     }
1992 
1993     /**
1994      * @throws NoSuchElementException {@inheritDoc}
1995      */
1996     public K firstKey() {
1997         Node<K,V> n = findFirst();
1998         if (n == null)
1999             throw new NoSuchElementException();
2000         return n.key;
2001     }
2002 
2003     /**
2004      * @throws NoSuchElementException {@inheritDoc}
2005      */
2006     public K lastKey() {
2007         Node<K,V> n = findLast();
2008         if (n == null)
2009             throw new NoSuchElementException();
2010         return n.key;
2011     }
2012 
2013     /**
2014      * @throws ClassCastException {@inheritDoc}
2015      * @throws NullPointerException if {@code fromKey} or {@code toKey} is null
2016      * @throws IllegalArgumentException {@inheritDoc}
2017      */
2018     public ConcurrentNavigableMap<K,V> subMap(K fromKey,
2019                                               boolean fromInclusive,
2020                                               K toKey,
2021                                               boolean toInclusive) {
2022         if (fromKey == null || toKey == null)
2023             throw new NullPointerException();
2024         return new SubMap<K,V>
2025             (this, fromKey, fromInclusive, toKey, toInclusive, false);
2026     }
2027 
2028     /**
2029      * @throws ClassCastException {@inheritDoc}
2030      * @throws NullPointerException if {@code toKey} is null
2031      * @throws IllegalArgumentException {@inheritDoc}
2032      */
2033     public ConcurrentNavigableMap<K,V> headMap(K toKey,
2034                                                boolean inclusive) {
2035         if (toKey == null)
2036             throw new NullPointerException();
2037         return new SubMap<K,V>
2038             (this, null, false, toKey, inclusive, false);
2039     }
2040 
2041     /**
2042      * @throws ClassCastException {@inheritDoc}
2043      * @throws NullPointerException if {@code fromKey} is null
2044      * @throws IllegalArgumentException {@inheritDoc}
2045      */
2046     public ConcurrentNavigableMap<K,V> tailMap(K fromKey,
2047                                                boolean inclusive) {
2048         if (fromKey == null)
2049             throw new NullPointerException();
2050         return new SubMap<K,V>
2051             (this, fromKey, inclusive, null, false, false);
2052     }
2053 
2054     /**
2055      * @throws ClassCastException {@inheritDoc}
2056      * @throws NullPointerException if {@code fromKey} or {@code toKey} is null
2057      * @throws IllegalArgumentException {@inheritDoc}
2058      */
2059     public ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey) {
2060         return subMap(fromKey, true, toKey, false);
2061     }
2062 
2063     /**
2064      * @throws ClassCastException {@inheritDoc}
2065      * @throws NullPointerException if {@code toKey} is null
2066      * @throws IllegalArgumentException {@inheritDoc}
2067      */
2068     public ConcurrentNavigableMap<K,V> headMap(K toKey) {
2069         return headMap(toKey, false);
2070     }
2071 
2072     /**
2073      * @throws ClassCastException {@inheritDoc}
2074      * @throws NullPointerException if {@code fromKey} is null
2075      * @throws IllegalArgumentException {@inheritDoc}
2076      */
2077     public ConcurrentNavigableMap<K,V> tailMap(K fromKey) {
2078         return tailMap(fromKey, true);
2079     }
2080 
2081     /* ---------------- Relational operations -------------- */
2082 
2083     /**
2084      * Returns a key-value mapping associated with the greatest key
2085      * strictly less than the given key, or <tt>null</tt> if there is
2086      * no such key. The returned entry does <em>not</em> support the
2087      * <tt>Entry.setValue</tt> method.
2088      *
2089      * @throws ClassCastException {@inheritDoc}
2090      * @throws NullPointerException if the specified key is null
2091      */
2092     public Map.Entry<K,V> lowerEntry(K key) {
2093         return getNear(key, LT);
2094     }
2095 
2096     /**
2097      * @throws ClassCastException {@inheritDoc}
2098      * @throws NullPointerException if the specified key is null
2099      */
2100     public K lowerKey(K key) {
2101         Node<K,V> n = findNear(key, LT);
2102         return (n == null)? null : n.key;
2103     }
2104 
2105     /**
2106      * Returns a key-value mapping associated with the greatest key
2107      * less than or equal to the given key, or <tt>null</tt> if there
2108      * is no such key. The returned entry does <em>not</em> support
2109      * the <tt>Entry.setValue</tt> method.
2110      *
2111      * @param key the key
2112      * @throws ClassCastException {@inheritDoc}
2113      * @throws NullPointerException if the specified key is null
2114      */
2115     public Map.Entry<K,V> floorEntry(K key) {
2116         return getNear(key, LT|EQ);
2117     }
2118 
2119     /**
2120      * @param key the key
2121      * @throws ClassCastException {@inheritDoc}
2122      * @throws NullPointerException if the specified key is null
2123      */
2124     public K floorKey(K key) {
2125         Node<K,V> n = findNear(key, LT|EQ);
2126         return (n == null)? null : n.key;
2127     }
2128 
2129     /**
2130      * Returns a key-value mapping associated with the least key
2131      * greater than or equal to the given key, or <tt>null</tt> if
2132      * there is no such entry. The returned entry does <em>not</em>
2133      * support the <tt>Entry.setValue</tt> method.
2134      *
2135      * @throws ClassCastException {@inheritDoc}
2136      * @throws NullPointerException if the specified key is null
2137      */
2138     public Map.Entry<K,V> ceilingEntry(K key) {
2139         return getNear(key, GT|EQ);
2140     }
2141 
2142     /**
2143      * @throws ClassCastException {@inheritDoc}
2144      * @throws NullPointerException if the specified key is null
2145      */
2146     public K ceilingKey(K key) {
2147         Node<K,V> n = findNear(key, GT|EQ);
2148         return (n == null)? null : n.key;
2149     }
2150 
2151     /**
2152      * Returns a key-value mapping associated with the least key
2153      * strictly greater than the given key, or <tt>null</tt> if there
2154      * is no such key. The returned entry does <em>not</em> support
2155      * the <tt>Entry.setValue</tt> method.
2156      *
2157      * @param key the key
2158      * @throws ClassCastException {@inheritDoc}
2159      * @throws NullPointerException if the specified key is null
2160      */
2161     public Map.Entry<K,V> higherEntry(K key) {
2162         return getNear(key, GT);
2163     }
2164 
2165     /**
2166      * @param key the key
2167      * @throws ClassCastException {@inheritDoc}
2168      * @throws NullPointerException if the specified key is null
2169      */
2170     public K higherKey(K key) {
2171         Node<K,V> n = findNear(key, GT);
2172         return (n == null)? null : n.key;
2173     }
2174 
2175     /**
2176      * Returns a key-value mapping associated with the least
2177      * key in this map, or <tt>null</tt> if the map is empty.
2178      * The returned entry does <em>not</em> support
2179      * the <tt>Entry.setValue</tt> method.
2180      */
2181     public Map.Entry<K,V> firstEntry() {
2182         for (;;) {
2183             Node<K,V> n = findFirst();
2184             if (n == null)
2185                 return null;
2186             AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
2187             if (e != null)
2188                 return e;
2189         }
2190     }
2191 
2192     /**
2193      * Returns a key-value mapping associated with the greatest
2194      * key in this map, or <tt>null</tt> if the map is empty.
2195      * The returned entry does <em>not</em> support
2196      * the <tt>Entry.setValue</tt> method.
2197      */
2198     public Map.Entry<K,V> lastEntry() {
2199         for (;;) {
2200             Node<K,V> n = findLast();
2201             if (n == null)
2202                 return null;
2203             AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
2204             if (e != null)
2205                 return e;
2206         }
2207     }
2208 
2209     /**
2210      * Removes and returns a key-value mapping associated with
2211      * the least key in this map, or <tt>null</tt> if the map is empty.
2212      * The returned entry does <em>not</em> support
2213      * the <tt>Entry.setValue</tt> method.
2214      */
2215     public Map.Entry<K,V> pollFirstEntry() {
2216         return doRemoveFirstEntry();
2217     }
2218 
2219     /**
2220      * Removes and returns a key-value mapping associated with
2221      * the greatest key in this map, or <tt>null</tt> if the map is empty.
2222      * The returned entry does <em>not</em> support
2223      * the <tt>Entry.setValue</tt> method.
2224      */
2225     public Map.Entry<K,V> pollLastEntry() {
2226         return doRemoveLastEntry();
2227     }
2228 
2229 
2230     /* ---------------- Iterators -------------- */
2231 
2232     /**
2233      * Base of iterator classes:
2234      */
2235     abstract class Iter<T> implements Iterator<T> {
2236         /** the last node returned by next() */
2237         Node<K,V> lastReturned;
2238         /** the next node to return from next(); */
2239         Node<K,V> next;
2240         /** Cache of next value field to maintain weak consistency */
2241         V nextValue;
2242 
2243         /** Initializes ascending iterator for entire range. */
2244         Iter() {
2245             for (;;) {
2246                 next = findFirst();
2247                 if (next == null)
2248                     break;
2249                 Object x = next.value;
2250                 if (x != null && x != next) {
2251                     nextValue = (V) x;
2252                     break;
2253                 }
2254             }
2255         }
2256 
2257         public final boolean hasNext() {
2258             return next != null;
2259         }
2260 
2261         /** Advances next to higher entry. */
2262         final void advance() {
2263             if (next == null)
2264                 throw new NoSuchElementException();
2265             lastReturned = next;
2266             for (;;) {
2267                 next = next.next;
2268                 if (next == null)
2269                     break;
2270                 Object x = next.value;
2271                 if (x != null && x != next) {
2272                     nextValue = (V) x;
2273                     break;
2274                 }
2275             }
2276         }
2277 
2278         public void remove() {
2279             Node<K,V> l = lastReturned;
2280             if (l == null)
2281                 throw new IllegalStateException();
2282             // It would not be worth all of the overhead to directly
2283             // unlink from here. Using remove is fast enough.
2284             ConcurrentSkipListMap.this.remove(l.key);
2285             lastReturned = null;
2286         }
2287 
2288     }
2289 
2290     final class ValueIterator extends Iter<V> {
2291         public V next() {
2292             V v = nextValue;
2293             advance();
2294             return v;
2295         }
2296     }
2297 
2298     final class KeyIterator extends Iter<K> {
2299         public K next() {
2300             Node<K,V> n = next;
2301             advance();
2302             return n.key;
2303         }
2304     }
2305 
2306     final class EntryIterator extends Iter<Map.Entry<K,V>> {
2307         public Map.Entry<K,V> next() {
2308             Node<K,V> n = next;
2309             V v = nextValue;
2310             advance();
2311             return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
2312         }
2313     }
2314 
2315     // Factory methods for iterators needed by ConcurrentSkipListSet etc
2316 
2317     Iterator<K> keyIterator() {
2318         return new KeyIterator();
2319     }
2320 
2321     Iterator<V> valueIterator() {
2322         return new ValueIterator();
2323     }
2324 
2325     Iterator<Map.Entry<K,V>> entryIterator() {
2326         return new EntryIterator();
2327     }
2328 
2329     /* ---------------- View Classes -------------- */
2330 
2331     /*
2332      * View classes are static, delegating to a ConcurrentNavigableMap
2333      * to allow use by SubMaps, which outweighs the ugliness of
2334      * needing type-tests for Iterator methods.
2335      */
2336 
2337     static final <E> List<E> toList(Collection<E> c) {
2338         // Using size() here would be a pessimization.
2339         List<E> list = new ArrayList<E>();
2340         for (E e : c)
2341             list.add(e);
2342         return list;
2343     }
2344 
2345     static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {

2346         private final ConcurrentNavigableMap<E,Object> m;
2347         KeySet(ConcurrentNavigableMap<E,Object> map) { m = map; }
2348         public int size() { return m.size(); }
2349         public boolean isEmpty() { return m.isEmpty(); }
2350         public boolean contains(Object o) { return m.containsKey(o); }
2351         public boolean remove(Object o) { return m.remove(o) != null; }
2352         public void clear() { m.clear(); }
2353         public E lower(E e) { return m.lowerKey(e); }
2354         public E floor(E e) { return m.floorKey(e); }
2355         public E ceiling(E e) { return m.ceilingKey(e); }
2356         public E higher(E e) { return m.higherKey(e); }
2357         public Comparator<? super E> comparator() { return m.comparator(); }
2358         public E first() { return m.firstKey(); }
2359         public E last() { return m.lastKey(); }
2360         public E pollFirst() {
2361             Map.Entry<E,Object> e = m.pollFirstEntry();
2362             return e == null? null : e.getKey();
2363         }
2364         public E pollLast() {
2365             Map.Entry<E,Object> e = m.pollLastEntry();
2366             return e == null? null : e.getKey();
2367         }
2368         public Iterator<E> iterator() {
2369             if (m instanceof ConcurrentSkipListMap)
2370                 return ((ConcurrentSkipListMap<E,Object>)m).keyIterator();
2371             else
2372                 return ((ConcurrentSkipListMap.SubMap<E,Object>)m).keyIterator();
2373         }
2374         public boolean equals(Object o) {
2375             if (o == this)
2376                 return true;
2377             if (!(o instanceof Set))
2378                 return false;
2379             Collection<?> c = (Collection<?>) o;
2380             try {
2381                 return containsAll(c) && c.containsAll(this);
2382             } catch (ClassCastException unused)   {
2383                 return false;
2384             } catch (NullPointerException unused) {
2385                 return false;
2386             }
2387         }
2388         public Object[] toArray()     { return toList(this).toArray();  }
2389         public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
2390         public Iterator<E> descendingIterator() {
2391             return descendingSet().iterator();
2392         }
2393         public NavigableSet<E> subSet(E fromElement,
2394                                       boolean fromInclusive,
2395                                       E toElement,
2396                                       boolean toInclusive) {
2397             return new KeySet<E>(m.subMap(fromElement, fromInclusive,
2398                                           toElement,   toInclusive));
2399         }
2400         public NavigableSet<E> headSet(E toElement, boolean inclusive) {
2401             return new KeySet<E>(m.headMap(toElement, inclusive));
2402         }
2403         public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
2404             return new KeySet<E>(m.tailMap(fromElement, inclusive));
2405         }
2406         public NavigableSet<E> subSet(E fromElement, E toElement) {
2407             return subSet(fromElement, true, toElement, false);
2408         }
2409         public NavigableSet<E> headSet(E toElement) {
2410             return headSet(toElement, false);
2411         }
2412         public NavigableSet<E> tailSet(E fromElement) {
2413             return tailSet(fromElement, true);
2414         }
2415         public NavigableSet<E> descendingSet() {
2416             return new KeySet(m.descendingMap());
2417         }
2418     }
2419 
2420     static final class Values<E> extends AbstractCollection<E> {
2421         private final ConcurrentNavigableMap<Object, E> m;
2422         Values(ConcurrentNavigableMap<Object, E> map) {
2423             m = map;
2424         }
2425         public Iterator<E> iterator() {
2426             if (m instanceof ConcurrentSkipListMap)
2427                 return ((ConcurrentSkipListMap<Object,E>)m).valueIterator();
2428             else
2429                 return ((SubMap<Object,E>)m).valueIterator();
2430         }
2431         public boolean isEmpty() {
2432             return m.isEmpty();
2433         }
2434         public int size() {
2435             return m.size();
2436         }
2437         public boolean contains(Object o) {
2438             return m.containsValue(o);
2439         }
2440         public void clear() {
2441             m.clear();
2442         }
2443         public Object[] toArray()     { return toList(this).toArray();  }
2444         public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
2445     }
2446 
2447     static final class EntrySet<K1,V1> extends AbstractSet<Map.Entry<K1,V1>> {
2448         private final ConcurrentNavigableMap<K1, V1> m;
2449         EntrySet(ConcurrentNavigableMap<K1, V1> map) {
2450             m = map;
2451         }
2452 
2453         public Iterator<Map.Entry<K1,V1>> iterator() {
2454             if (m instanceof ConcurrentSkipListMap)
2455                 return ((ConcurrentSkipListMap<K1,V1>)m).entryIterator();
2456             else
2457                 return ((SubMap<K1,V1>)m).entryIterator();
2458         }
2459 
2460         public boolean contains(Object o) {
2461             if (!(o instanceof Map.Entry))
2462                 return false;
2463             Map.Entry<K1,V1> e = (Map.Entry<K1,V1>)o;
2464             V1 v = m.get(e.getKey());
2465             return v != null && v.equals(e.getValue());
2466         }
2467         public boolean remove(Object o) {
2468             if (!(o instanceof Map.Entry))
2469                 return false;
2470             Map.Entry<K1,V1> e = (Map.Entry<K1,V1>)o;
2471             return m.remove(e.getKey(),
2472                             e.getValue());
2473         }
2474         public boolean isEmpty() {
2475             return m.isEmpty();
2476         }
2477         public int size() {
2478             return m.size();
2479         }
2480         public void clear() {
2481             m.clear();
2482         }
2483         public boolean equals(Object o) {
2484             if (o == this)
2485                 return true;
2486             if (!(o instanceof Set))
2487                 return false;
2488             Collection<?> c = (Collection<?>) o;
2489             try {
2490                 return containsAll(c) && c.containsAll(this);
2491             } catch (ClassCastException unused)   {
2492                 return false;
2493             } catch (NullPointerException unused) {
2494                 return false;
2495             }
2496         }
2497         public Object[] toArray()     { return toList(this).toArray();  }
2498         public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
2499     }
2500 
2501     /**
2502      * Submaps returned by {@link ConcurrentSkipListMap} submap operations
2503      * represent a subrange of mappings of their underlying
2504      * maps. Instances of this class support all methods of their
2505      * underlying maps, differing in that mappings outside their range are
2506      * ignored, and attempts to add mappings outside their ranges result
2507      * in {@link IllegalArgumentException}.  Instances of this class are
2508      * constructed only using the <tt>subMap</tt>, <tt>headMap</tt>, and
2509      * <tt>tailMap</tt> methods of their underlying maps.
2510      *
2511      * @serial include
2512      */
2513     static final class SubMap<K,V> extends AbstractMap<K,V>
2514         implements ConcurrentNavigableMap<K,V>, Cloneable,
2515                    java.io.Serializable {
2516         private static final long serialVersionUID = -7647078645895051609L;
2517 
2518         /** Underlying map */
2519         private final ConcurrentSkipListMap<K,V> m;
2520         /** lower bound key, or null if from start */
2521         private final K lo;
2522         /** upper bound key, or null if to end */
2523         private final K hi;
2524         /** inclusion flag for lo */
2525         private final boolean loInclusive;
2526         /** inclusion flag for hi */
2527         private final boolean hiInclusive;
2528         /** direction */
2529         private final boolean isDescending;
2530 
2531         // Lazily initialized view holders
2532         private transient KeySet<K> keySetView;
2533         private transient Set<Map.Entry<K,V>> entrySetView;
2534         private transient Collection<V> valuesView;
2535 
2536         /**
2537          * Creates a new submap, initializing all fields
2538          */
2539         SubMap(ConcurrentSkipListMap<K,V> map,
2540                K fromKey, boolean fromInclusive,
2541                K toKey, boolean toInclusive,
2542                boolean isDescending) {
2543             if (fromKey != null && toKey != null &&
2544                 map.compare(fromKey, toKey) > 0)
2545                 throw new IllegalArgumentException("inconsistent range");
2546             this.m = map;
2547             this.lo = fromKey;
2548             this.hi = toKey;
2549             this.loInclusive = fromInclusive;
2550             this.hiInclusive = toInclusive;
2551             this.isDescending = isDescending;
2552         }
2553 
2554         /* ----------------  Utilities -------------- */
2555 
2556         private boolean tooLow(K key) {
2557             if (lo != null) {
2558                 int c = m.compare(key, lo);
2559                 if (c < 0 || (c == 0 && !loInclusive))
2560                     return true;
2561             }
2562             return false;
2563         }
2564 
2565         private boolean tooHigh(K key) {
2566             if (hi != null) {
2567                 int c = m.compare(key, hi);
2568                 if (c > 0 || (c == 0 && !hiInclusive))
2569                     return true;
2570             }
2571             return false;
2572         }
2573 
2574         private boolean inBounds(K key) {
2575             return !tooLow(key) && !tooHigh(key);
2576         }
2577 
2578         private void checkKeyBounds(K key) throws IllegalArgumentException {
2579             if (key == null)
2580                 throw new NullPointerException();
2581             if (!inBounds(key))
2582                 throw new IllegalArgumentException("key out of range");
2583         }
2584 
2585         /**
2586          * Returns true if node key is less than upper bound of range
2587          */
2588         private boolean isBeforeEnd(ConcurrentSkipListMap.Node<K,V> n) {
2589             if (n == null)
2590                 return false;
2591             if (hi == null)
2592                 return true;
2593             K k = n.key;
2594             if (k == null) // pass by markers and headers
2595                 return true;
2596             int c = m.compare(k, hi);
2597             if (c > 0 || (c == 0 && !hiInclusive))
2598                 return false;
2599             return true;
2600         }
2601 
2602         /**
2603          * Returns lowest node. This node might not be in range, so
2604          * most usages need to check bounds
2605          */
2606         private ConcurrentSkipListMap.Node<K,V> loNode() {
2607             if (lo == null)
2608                 return m.findFirst();
2609             else if (loInclusive)
2610                 return m.findNear(lo, m.GT|m.EQ);
2611             else
2612                 return m.findNear(lo, m.GT);
2613         }
2614 
2615         /**
2616          * Returns highest node. This node might not be in range, so
2617          * most usages need to check bounds
2618          */
2619         private ConcurrentSkipListMap.Node<K,V> hiNode() {
2620             if (hi == null)
2621                 return m.findLast();
2622             else if (hiInclusive)
2623                 return m.findNear(hi, m.LT|m.EQ);
2624             else
2625                 return m.findNear(hi, m.LT);
2626         }
2627 
2628         /**
2629          * Returns lowest absolute key (ignoring directonality)
2630          */
2631         private K lowestKey() {
2632             ConcurrentSkipListMap.Node<K,V> n = loNode();
2633             if (isBeforeEnd(n))
2634                 return n.key;
2635             else
2636                 throw new NoSuchElementException();
2637         }
2638 
2639         /**
2640          * Returns highest absolute key (ignoring directonality)
2641          */
2642         private K highestKey() {
2643             ConcurrentSkipListMap.Node<K,V> n = hiNode();
2644             if (n != null) {
2645                 K last = n.key;
2646                 if (inBounds(last))
2647                     return last;
2648             }
2649             throw new NoSuchElementException();
2650         }
2651 
2652         private Map.Entry<K,V> lowestEntry() {
2653             for (;;) {
2654                 ConcurrentSkipListMap.Node<K,V> n = loNode();
2655                 if (!isBeforeEnd(n))
2656                     return null;
2657                 Map.Entry<K,V> e = n.createSnapshot();
2658                 if (e != null)
2659                     return e;
2660             }
2661         }
2662 
2663         private Map.Entry<K,V> highestEntry() {
2664             for (;;) {
2665                 ConcurrentSkipListMap.Node<K,V> n = hiNode();
2666                 if (n == null || !inBounds(n.key))
2667                     return null;
2668                 Map.Entry<K,V> e = n.createSnapshot();
2669                 if (e != null)
2670                     return e;
2671             }
2672         }
2673 
2674         private Map.Entry<K,V> removeLowest() {
2675             for (;;) {
2676                 Node<K,V> n = loNode();
2677                 if (n == null)
2678                     return null;
2679                 K k = n.key;
2680                 if (!inBounds(k))
2681                     return null;
2682                 V v = m.doRemove(k, null);
2683                 if (v != null)
2684                     return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2685             }
2686         }
2687 
2688         private Map.Entry<K,V> removeHighest() {
2689             for (;;) {
2690                 Node<K,V> n = hiNode();
2691                 if (n == null)
2692                     return null;
2693                 K k = n.key;
2694                 if (!inBounds(k))
2695                     return null;
2696                 V v = m.doRemove(k, null);
2697                 if (v != null)
2698                     return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2699             }
2700         }
2701 
2702         /**
2703          * Submap version of ConcurrentSkipListMap.getNearEntry
2704          */
2705         private Map.Entry<K,V> getNearEntry(K key, int rel) {
2706             if (isDescending) { // adjust relation for direction
2707                 if ((rel & m.LT) == 0)
2708                     rel |= m.LT;
2709                 else
2710                     rel &= ~m.LT;
2711             }
2712             if (tooLow(key))
2713                 return ((rel & m.LT) != 0)? null : lowestEntry();
2714             if (tooHigh(key))
2715                 return ((rel & m.LT) != 0)? highestEntry() : null;
2716             for (;;) {
2717                 Node<K,V> n = m.findNear(key, rel);
2718                 if (n == null || !inBounds(n.key))
2719                     return null;
2720                 K k = n.key;
2721                 V v = n.getValidValue();
2722                 if (v != null)
2723                     return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2724             }
2725         }
2726 
2727         // Almost the same as getNearEntry, except for keys
2728         private K getNearKey(K key, int rel) {
2729             if (isDescending) { // adjust relation for direction
2730                 if ((rel & m.LT) == 0)
2731                     rel |= m.LT;
2732                 else
2733                     rel &= ~m.LT;
2734             }
2735             if (tooLow(key)) {
2736                 if ((rel & m.LT) == 0) {
2737                     ConcurrentSkipListMap.Node<K,V> n = loNode();
2738                     if (isBeforeEnd(n))
2739                         return n.key;
2740                 }
2741                 return null;
2742             }
2743             if (tooHigh(key)) {
2744                 if ((rel & m.LT) != 0) {
2745                     ConcurrentSkipListMap.Node<K,V> n = hiNode();
2746                     if (n != null) {
2747                         K last = n.key;
2748                         if (inBounds(last))
2749                             return last;
2750                     }
2751                 }
2752                 return null;
2753             }
2754             for (;;) {
2755                 Node<K,V> n = m.findNear(key, rel);
2756                 if (n == null || !inBounds(n.key))
2757                     return null;
2758                 K k = n.key;
2759                 V v = n.getValidValue();
2760                 if (v != null)
2761                     return k;
2762             }
2763         }
2764 
2765         /* ----------------  Map API methods -------------- */
2766 
2767         public boolean containsKey(Object key) {
2768             if (key == null) throw new NullPointerException();
2769             K k = (K)key;
2770             return inBounds(k) && m.containsKey(k);
2771         }
2772 
2773         public V get(Object key) {
2774             if (key == null) throw new NullPointerException();
2775             K k = (K)key;
2776             return ((!inBounds(k)) ? null : m.get(k));
2777         }
2778 
2779         public V put(K key, V value) {
2780             checkKeyBounds(key);
2781             return m.put(key, value);
2782         }
2783 
2784         public V remove(Object key) {
2785             K k = (K)key;
2786             return (!inBounds(k))? null : m.remove(k);
2787         }
2788 
2789         public int size() {
2790             long count = 0;
2791             for (ConcurrentSkipListMap.Node<K,V> n = loNode();
2792                  isBeforeEnd(n);
2793                  n = n.next) {
2794                 if (n.getValidValue() != null)
2795                     ++count;
2796             }
2797             return count >= Integer.MAX_VALUE? Integer.MAX_VALUE : (int)count;
2798         }
2799 
2800         public boolean isEmpty() {
2801             return !isBeforeEnd(loNode());
2802         }
2803 
2804         public boolean containsValue(Object value) {
2805             if (value == null)
2806                 throw new NullPointerException();
2807             for (ConcurrentSkipListMap.Node<K,V> n = loNode();
2808                  isBeforeEnd(n);
2809                  n = n.next) {
2810                 V v = n.getValidValue();
2811                 if (v != null && value.equals(v))
2812                     return true;
2813             }
2814             return false;
2815         }
2816 
2817         public void clear() {
2818             for (ConcurrentSkipListMap.Node<K,V> n = loNode();
2819                  isBeforeEnd(n);
2820                  n = n.next) {
2821                 if (n.getValidValue() != null)
2822                     m.remove(n.key);
2823             }
2824         }
2825 
2826         /* ----------------  ConcurrentMap API methods -------------- */
2827 
2828         public V putIfAbsent(K key, V value) {
2829             checkKeyBounds(key);
2830             return m.putIfAbsent(key, value);
2831         }
2832 
2833         public boolean remove(Object key, Object value) {
2834             K k = (K)key;
2835             return inBounds(k) && m.remove(k, value);
2836         }
2837 
2838         public boolean replace(K key, V oldValue, V newValue) {
2839             checkKeyBounds(key);
2840             return m.replace(key, oldValue, newValue);
2841         }
2842 
2843         public V replace(K key, V value) {
2844             checkKeyBounds(key);
2845             return m.replace(key, value);
2846         }
2847 
2848         /* ----------------  SortedMap API methods -------------- */
2849 
2850         public Comparator<? super K> comparator() {
2851             Comparator<? super K> cmp = m.comparator();
2852             if (isDescending)
2853                 return Collections.reverseOrder(cmp);
2854             else
2855                 return cmp;
2856         }
2857 
2858         /**
2859          * Utility to create submaps, where given bounds override
2860          * unbounded(null) ones and/or are checked against bounded ones.
2861          */
2862         private SubMap<K,V> newSubMap(K fromKey,
2863                                       boolean fromInclusive,
2864                                       K toKey,
2865                                       boolean toInclusive) {
2866             if (isDescending) { // flip senses
2867                 K tk = fromKey;
2868                 fromKey = toKey;
2869                 toKey = tk;
2870                 boolean ti = fromInclusive;
2871                 fromInclusive = toInclusive;
2872                 toInclusive = ti;
2873             }
2874             if (lo != null) {
2875                 if (fromKey == null) {
2876                     fromKey = lo;
2877                     fromInclusive = loInclusive;
2878                 }
2879                 else {
2880                     int c = m.compare(fromKey, lo);
2881                     if (c < 0 || (c == 0 && !loInclusive && fromInclusive))
2882                         throw new IllegalArgumentException("key out of range");
2883                 }
2884             }
2885             if (hi != null) {
2886                 if (toKey == null) {
2887                     toKey = hi;
2888                     toInclusive = hiInclusive;
2889                 }
2890                 else {
2891                     int c = m.compare(toKey, hi);
2892                     if (c > 0 || (c == 0 && !hiInclusive && toInclusive))
2893                         throw new IllegalArgumentException("key out of range");
2894                 }
2895             }
2896             return new SubMap<K,V>(m, fromKey, fromInclusive,
2897                                    toKey, toInclusive, isDescending);
2898         }
2899 
2900         public SubMap<K,V> subMap(K fromKey,
2901                                   boolean fromInclusive,
2902                                   K toKey,
2903                                   boolean toInclusive) {
2904             if (fromKey == null || toKey == null)
2905                 throw new NullPointerException();
2906             return newSubMap(fromKey, fromInclusive, toKey, toInclusive);
2907         }
2908 
2909         public SubMap<K,V> headMap(K toKey,
2910                                    boolean inclusive) {
2911             if (toKey == null)
2912                 throw new NullPointerException();
2913             return newSubMap(null, false, toKey, inclusive);
2914         }
2915 
2916         public SubMap<K,V> tailMap(K fromKey,
2917                                    boolean inclusive) {
2918             if (fromKey == null)
2919                 throw new NullPointerException();
2920             return newSubMap(fromKey, inclusive, null, false);
2921         }
2922 
2923         public SubMap<K,V> subMap(K fromKey, K toKey) {
2924             return subMap(fromKey, true, toKey, false);
2925         }
2926 
2927         public SubMap<K,V> headMap(K toKey) {
2928             return headMap(toKey, false);
2929         }
2930 
2931         public SubMap<K,V> tailMap(K fromKey) {
2932             return tailMap(fromKey, true);
2933         }
2934 
2935         public SubMap<K,V> descendingMap() {
2936             return new SubMap<K,V>(m, lo, loInclusive,
2937                                    hi, hiInclusive, !isDescending);
2938         }
2939 
2940         /* ----------------  Relational methods -------------- */
2941 
2942         public Map.Entry<K,V> ceilingEntry(K key) {
2943             return getNearEntry(key, (m.GT|m.EQ));
2944         }
2945 
2946         public K ceilingKey(K key) {
2947             return getNearKey(key, (m.GT|m.EQ));
2948         }
2949 
2950         public Map.Entry<K,V> lowerEntry(K key) {
2951             return getNearEntry(key, (m.LT));
2952         }
2953 
2954         public K lowerKey(K key) {
2955             return getNearKey(key, (m.LT));
2956         }
2957 
2958         public Map.Entry<K,V> floorEntry(K key) {
2959             return getNearEntry(key, (m.LT|m.EQ));
2960         }
2961 
2962         public K floorKey(K key) {
2963             return getNearKey(key, (m.LT|m.EQ));
2964         }
2965 
2966         public Map.Entry<K,V> higherEntry(K key) {
2967             return getNearEntry(key, (m.GT));
2968         }
2969 
2970         public K higherKey(K key) {
2971             return getNearKey(key, (m.GT));
2972         }
2973 
2974         public K firstKey() {
2975             return isDescending? highestKey() : lowestKey();
2976         }
2977 
2978         public K lastKey() {
2979             return isDescending? lowestKey() : highestKey();
2980         }
2981 
2982         public Map.Entry<K,V> firstEntry() {
2983             return isDescending? highestEntry() : lowestEntry();
2984         }
2985 
2986         public Map.Entry<K,V> lastEntry() {
2987             return isDescending? lowestEntry() : highestEntry();
2988         }
2989 
2990         public Map.Entry<K,V> pollFirstEntry() {
2991             return isDescending? removeHighest() : removeLowest();
2992         }
2993 
2994         public Map.Entry<K,V> pollLastEntry() {
2995             return isDescending? removeLowest() : removeHighest();
2996         }
2997 
2998         /* ---------------- Submap Views -------------- */
2999 
3000         public NavigableSet<K> keySet() {
3001             KeySet<K> ks = keySetView;
3002             return (ks != null) ? ks : (keySetView = new KeySet(this));
3003         }
3004 
3005         public NavigableSet<K> navigableKeySet() {
3006             KeySet<K> ks = keySetView;
3007             return (ks != null) ? ks : (keySetView = new KeySet(this));
3008         }
3009 
3010         public Collection<V> values() {
3011             Collection<V> vs = valuesView;
3012             return (vs != null) ? vs : (valuesView = new Values(this));
3013         }
3014 
3015         public Set<Map.Entry<K,V>> entrySet() {
3016             Set<Map.Entry<K,V>> es = entrySetView;
3017             return (es != null) ? es : (entrySetView = new EntrySet(this));
3018         }
3019 
3020         public NavigableSet<K> descendingKeySet() {
3021             return descendingMap().navigableKeySet();
3022         }
3023 
3024         Iterator<K> keyIterator() {
3025             return new SubMapKeyIterator();
3026         }
3027 
3028         Iterator<V> valueIterator() {
3029             return new SubMapValueIterator();
3030         }
3031 
3032         Iterator<Map.Entry<K,V>> entryIterator() {
3033             return new SubMapEntryIterator();
3034         }
3035 
3036         /**
3037          * Variant of main Iter class to traverse through submaps.
3038          */
3039         abstract class SubMapIter<T> implements Iterator<T> {
3040             /** the last node returned by next() */
3041             Node<K,V> lastReturned;
3042             /** the next node to return from next(); */
3043             Node<K,V> next;
3044             /** Cache of next value field to maintain weak consistency */
3045             V nextValue;
3046 
3047             SubMapIter() {
3048                 for (;;) {
3049                     next = isDescending ? hiNode() : loNode();
3050                     if (next == null)
3051                         break;
3052                     Object x = next.value;
3053                     if (x != null && x != next) {
3054                         if (! inBounds(next.key))
3055                             next = null;
3056                         else
3057                             nextValue = (V) x;
3058                         break;
3059                     }
3060                 }
3061             }
3062 
3063             public final boolean hasNext() {
3064                 return next != null;
3065             }
3066 
3067             final void advance() {
3068                 if (next == null)
3069                     throw new NoSuchElementException();
3070                 lastReturned = next;
3071                 if (isDescending)
3072                     descend();
3073                 else
3074                     ascend();
3075             }
3076 
3077             private void ascend() {
3078                 for (;;) {
3079                     next = next.next;
3080                     if (next == null)
3081                         break;
3082                     Object x = next.value;
3083                     if (x != null && x != next) {
3084                         if (tooHigh(next.key))
3085                             next = null;
3086                         else
3087                             nextValue = (V) x;
3088                         break;
3089                     }
3090                 }
3091             }
3092 
3093             private void descend() {
3094                 for (;;) {
3095                     next = m.findNear(lastReturned.key, LT);
3096                     if (next == null)
3097                         break;
3098                     Object x = next.value;
3099                     if (x != null && x != next) {
3100                         if (tooLow(next.key))
3101                             next = null;
3102                         else
3103                             nextValue = (V) x;
3104                         break;
3105                     }
3106                 }
3107             }
3108 
3109             public void remove() {
3110                 Node<K,V> l = lastReturned;
3111                 if (l == null)
3112                     throw new IllegalStateException();
3113                 m.remove(l.key);
3114                 lastReturned = null;
3115             }
3116 
3117         }
3118 
3119         final class SubMapValueIterator extends SubMapIter<V> {
3120             public V next() {
3121                 V v = nextValue;
3122                 advance();
3123                 return v;
3124             }
3125         }
3126 
3127         final class SubMapKeyIterator extends SubMapIter<K> {
3128             public K next() {
3129                 Node<K,V> n = next;
3130                 advance();
3131                 return n.key;
3132             }
3133         }
3134 
3135         final class SubMapEntryIterator extends SubMapIter<Map.Entry<K,V>> {
3136             public Map.Entry<K,V> next() {
3137                 Node<K,V> n = next;
3138                 V v = nextValue;
3139                 advance();
3140                 return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
3141             }
3142         }
3143     }


















3144 }
--- EOF ---