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

Save This Page
Home » openjdk-7 » java » util » concurrent » [javadoc | source]