src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java

Print this page




  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  *


  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              |                        |


 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


 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> {


 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     }


 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;


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);


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)


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


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;


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);


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;


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             }


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.


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 }


  18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  19  *
  20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  21  * or visit www.oracle.com if you need additional information or have any
  22  * questions.
  23  */
  24 
  25 /*
  26  * This file is available under and governed by the GNU General Public
  27  * License version 2 only, as published by the Free Software Foundation.
  28  * However, the following notice accompanied the original version of this
  29  * file:
  30  *
  31  * Written by Doug Lea with assistance from members of JCP JSR-166
  32  * Expert Group and released to the public domain, as explained at
  33  * http://creativecommons.org/publicdomain/zero/1.0/
  34  */
  35 
  36 package java.util.concurrent;
  37 import java.util.*;

  38 
  39 /**
  40  * A scalable concurrent {@link ConcurrentNavigableMap} implementation.
  41  * The map is sorted according to the {@linkplain Comparable natural
  42  * ordering} of its keys, or by a {@link Comparator} provided at map
  43  * creation time, depending on which constructor is used.
  44  *
  45  * <p>This class implements a concurrent variant of <a
  46  * href="http://en.wikipedia.org/wiki/Skip_list" target="_top">SkipLists</a>
  47  * providing expected average <i>log(n)</i> time cost for the
  48  * <tt>containsKey</tt>, <tt>get</tt>, <tt>put</tt> and
  49  * <tt>remove</tt> operations and their variants.  Insertion, removal,
  50  * update, and access operations safely execute concurrently by
  51  * multiple threads.  Iterators are <i>weakly consistent</i>, returning
  52  * elements reflecting the state of the map at some point at or since
  53  * the creation of the iterator.  They do <em>not</em> throw {@link
  54  * ConcurrentModificationException}, and may proceed concurrently with
  55  * other operations. Ascending key ordered views and their iterators
  56  * are faster than descending ones.
  57  *


  72  * <em>not</em> guaranteed to be performed atomically. For example, an
  73  * iterator operating concurrently with a <tt>putAll</tt> operation
  74  * might view only some of the added elements.
  75  *
  76  * <p>This class and its views and iterators implement all of the
  77  * <em>optional</em> methods of the {@link Map} and {@link Iterator}
  78  * interfaces. Like most other concurrent collections, this class does
  79  * <em>not</em> permit the use of <tt>null</tt> keys or values because some
  80  * null return values cannot be reliably distinguished from the absence of
  81  * elements.
  82  *
  83  * <p>This class is a member of the
  84  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  85  * Java Collections Framework</a>.
  86  *
  87  * @author Doug Lea
  88  * @param <K> the type of keys maintained by this map
  89  * @param <V> the type of mapped values
  90  * @since 1.6
  91  */
  92 @SuppressWarnings("unchecked")
  93 public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
  94     implements ConcurrentNavigableMap<K,V>,
  95                Cloneable,
  96                java.io.Serializable {
  97     /*
  98      * This class implements a tree-like two-dimensionally linked skip
  99      * list in which the index levels are represented in separate
 100      * nodes from the base nodes holding data.  There are two reasons
 101      * for taking this approach instead of the usual array-based
 102      * structure: 1) Array based implementations seem to encounter
 103      * more complexity and overhead 2) We can use cheaper algorithms
 104      * for the heavily-traversed index lists than can be used for the
 105      * base lists.  Here's a picture of some of the basics for a
 106      * possible list with 2 levels of index:
 107      *
 108      * Head nodes          Index nodes
 109      * +-+    right        +-+                      +-+
 110      * |2|---------------->| |--------------------->| |->null
 111      * +-+                 +-+                      +-+
 112      *  | down              |                        |


 335 
 336     /**
 337      * The topmost head index of the skiplist.
 338      */
 339     private transient volatile HeadIndex<K,V> head;
 340 
 341     /**
 342      * The comparator used to maintain order in this map, or null
 343      * if using natural ordering.
 344      * @serial
 345      */
 346     private final Comparator<? super K> comparator;
 347 
 348     /**
 349      * Seed for simple random number generator.  Not volatile since it
 350      * doesn't matter too much if different threads don't see updates.
 351      */
 352     private transient int randomSeed;
 353 
 354     /** Lazily initialized key set */
 355     private transient KeySet<K> keySet;
 356     /** Lazily initialized entry set */
 357     private transient EntrySet<K,V> entrySet;
 358     /** Lazily initialized values collection */
 359     private transient Values<V> values;
 360     /** Lazily initialized descending key set */
 361     private transient ConcurrentNavigableMap<K,V> descendingMap;
 362 
 363     /**
 364      * Initializes or resets state. Needed by constructors, clone,
 365      * clear, readObject. and ConcurrentSkipListSet.clone.
 366      * (Note that comparator must be separately initialized.)
 367      */
 368     final void initialize() {
 369         keySet = null;
 370         entrySet = null;
 371         values = null;
 372         descendingMap = null;
 373         randomSeed = seedGenerator.nextInt() | 0x0100; // ensure nonzero
 374         head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),
 375                                   null, null, 1);
 376     }
 377 
 378     /**
 379      * compareAndSet head node


 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> {


 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     }


 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;


1419      * same ordering as the specified sorted map.
1420      *
1421      * @param m the sorted map whose mappings are to be placed in this
1422      *        map, and whose comparator is to be used to sort this map
1423      * @throws NullPointerException if the specified sorted map or any of
1424      *         its keys or values are null
1425      */
1426     public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) {
1427         this.comparator = m.comparator();
1428         initialize();
1429         buildFromSorted(m);
1430     }
1431 
1432     /**
1433      * Returns a shallow copy of this <tt>ConcurrentSkipListMap</tt>
1434      * instance. (The keys and values themselves are not cloned.)
1435      *
1436      * @return a shallow copy of this map
1437      */
1438     public ConcurrentSkipListMap<K,V> clone() {

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


1443             clone.initialize();
1444             clone.buildFromSorted(this);
1445             return clone;
1446         } catch (CloneNotSupportedException e) {
1447             throw new InternalError();
1448         }
1449     }
1450 
1451     /**
1452      * Streamlined bulk insertion to initialize from elements of
1453      * given sorted map.  Call only from constructor or clone
1454      * method.
1455      */
1456     private void buildFromSorted(SortedMap<K, ? extends V> map) {
1457         if (map == null)
1458             throw new NullPointerException();
1459 
1460         HeadIndex<K,V> h = head;
1461         Node<K,V> basepred = h.node;
1462 
1463         // Track the current rightmost node at each level. Uses an
1464         // ArrayList to avoid committing to initial or maximum level.
1465         ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>();
1466 
1467         // initialize
1468         for (int i = 0; i <= h.level; ++i)
1469             preds.add(null);


1490                 Index<K,V> idx = null;
1491                 for (int i = 1; i <= j; ++i) {
1492                     idx = new Index<K,V>(z, idx, null);
1493                     if (i > h.level)
1494                         h = new HeadIndex<K,V>(h.node, h, idx, i);
1495 
1496                     if (i < preds.size()) {
1497                         preds.get(i).right = idx;
1498                         preds.set(i, idx);
1499                     } else
1500                         preds.add(idx);
1501                 }
1502             }
1503         }
1504         head = h;
1505     }
1506 
1507     /* ---------------- Serialization -------------- */
1508 
1509     /**
1510      * Saves the state of this map to a stream (that is, serializes it).
1511      *
1512      * @serialData The key (Object) and value (Object) for each
1513      * key-value mapping represented by the map, followed by
1514      * <tt>null</tt>. The key-value mappings are emitted in key-order
1515      * (as determined by the Comparator, or by the keys' natural
1516      * ordering if no Comparator).
1517      */
1518     private void writeObject(java.io.ObjectOutputStream s)
1519         throws java.io.IOException {
1520         // Write out the Comparator and any hidden stuff
1521         s.defaultWriteObject();
1522 
1523         // Write out keys and values (alternating)
1524         for (Node<K,V> n = findFirst(); n != null; n = n.next) {
1525             V v = n.getValidValue();
1526             if (v != null) {
1527                 s.writeObject(n.key);
1528                 s.writeObject(v);
1529             }
1530         }
1531         s.writeObject(null);
1532     }
1533 
1534     /**
1535      * Reconstitutes the map from a stream (that is, deserializes it).
1536      *
1537      * @param s the stream
1538      */
1539     private void readObject(final java.io.ObjectInputStream s)
1540         throws java.io.IOException, ClassNotFoundException {
1541         // Read in the Comparator and any hidden stuff
1542         s.defaultReadObject();
1543         // Reset transients
1544         initialize();
1545 
1546         /*
1547          * This is nearly identical to buildFromSorted, but is
1548          * distinct because readObject calls can't be nicely adapted
1549          * as the kind of iterator needed by buildFromSorted. (They
1550          * can be, but doing so requires type cheats and/or creation
1551          * of adaptor classes.) It is simpler to just adapt the code.
1552          */
1553 
1554         HeadIndex<K,V> h = head;
1555         Node<K,V> basepred = h.node;
1556         ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>();
1557         for (int i = 0; i <= h.level; ++i)


1740      * The set's iterator returns the keys in ascending order.
1741      * The set is backed by the map, so changes to the map are
1742      * reflected in the set, and vice-versa.  The set supports element
1743      * removal, which removes the corresponding mapping from the map,
1744      * via the {@code Iterator.remove}, {@code Set.remove},
1745      * {@code removeAll}, {@code retainAll}, and {@code clear}
1746      * operations.  It does not support the {@code add} or {@code addAll}
1747      * operations.
1748      *
1749      * <p>The view's {@code iterator} is a "weakly consistent" iterator
1750      * that will never throw {@link ConcurrentModificationException},
1751      * and guarantees to traverse elements as they existed upon
1752      * construction of the iterator, and may (but is not guaranteed to)
1753      * reflect any modifications subsequent to construction.
1754      *
1755      * <p>This method is equivalent to method {@code navigableKeySet}.
1756      *
1757      * @return a navigable set view of the keys in this map
1758      */
1759     public NavigableSet<K> keySet() {
1760         KeySet<K> ks = keySet;
1761         return (ks != null) ? ks : (keySet = new KeySet<K>(this));
1762     }
1763 
1764     public NavigableSet<K> navigableKeySet() {
1765         KeySet<K> ks = keySet;
1766         return (ks != null) ? ks : (keySet = new KeySet<K>(this));
1767     }
1768 
1769     /**
1770      * Returns a {@link Collection} view of the values contained in this map.
1771      * The collection's iterator returns the values in ascending order
1772      * of the corresponding keys.
1773      * The collection is backed by the map, so changes to the map are
1774      * reflected in the collection, and vice-versa.  The collection
1775      * supports element removal, which removes the corresponding
1776      * mapping from the map, via the <tt>Iterator.remove</tt>,
1777      * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1778      * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
1779      * support the <tt>add</tt> or <tt>addAll</tt> operations.
1780      *
1781      * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1782      * that will never throw {@link ConcurrentModificationException},
1783      * and guarantees to traverse elements as they existed upon
1784      * construction of the iterator, and may (but is not guaranteed to)
1785      * reflect any modifications subsequent to construction.
1786      */
1787     public Collection<V> values() {
1788         Values<V> vs = values;
1789         return (vs != null) ? vs : (values = new Values<V>(this));
1790     }
1791 
1792     /**
1793      * Returns a {@link Set} view of the mappings contained in this map.
1794      * The set's iterator returns the entries in ascending key order.
1795      * The set is backed by the map, so changes to the map are
1796      * reflected in the set, and vice-versa.  The set supports element
1797      * removal, which removes the corresponding mapping from the map,
1798      * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1799      * <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
1800      * operations.  It does not support the <tt>add</tt> or
1801      * <tt>addAll</tt> operations.
1802      *
1803      * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1804      * that will never throw {@link ConcurrentModificationException},
1805      * and guarantees to traverse elements as they existed upon
1806      * construction of the iterator, and may (but is not guaranteed to)
1807      * reflect any modifications subsequent to construction.
1808      *
1809      * <p>The <tt>Map.Entry</tt> elements returned by
1810      * <tt>iterator.next()</tt> do <em>not</em> support the
1811      * <tt>setValue</tt> operation.
1812      *
1813      * @return a set view of the mappings contained in this map,
1814      *         sorted in ascending key order
1815      */
1816     public Set<Map.Entry<K,V>> entrySet() {
1817         EntrySet<K,V> es = entrySet;
1818         return (es != null) ? es : (entrySet = new EntrySet<K,V>(this));
1819     }
1820 
1821     public ConcurrentNavigableMap<K,V> descendingMap() {
1822         ConcurrentNavigableMap<K,V> dm = descendingMap;
1823         return (dm != null) ? dm : (descendingMap = new SubMap<K,V>
1824                                     (this, null, false, null, false, true));
1825     }
1826 
1827     public NavigableSet<K> descendingKeySet() {
1828         return descendingMap().navigableKeySet();
1829     }
1830 
1831     /* ---------------- AbstractMap Overrides -------------- */
1832 
1833     /**
1834      * Compares the specified object with this map for equality.
1835      * Returns <tt>true</tt> if the given object is also a map and the
1836      * two maps represent the same mappings.  More formally, two maps
1837      * <tt>m1</tt> and <tt>m2</tt> represent the same mappings if
1838      * <tt>m1.entrySet().equals(m2.entrySet())</tt>.  This


2289     }
2290 
2291     /* ---------------- View Classes -------------- */
2292 
2293     /*
2294      * View classes are static, delegating to a ConcurrentNavigableMap
2295      * to allow use by SubMaps, which outweighs the ugliness of
2296      * needing type-tests for Iterator methods.
2297      */
2298 
2299     static final <E> List<E> toList(Collection<E> c) {
2300         // Using size() here would be a pessimization.
2301         List<E> list = new ArrayList<E>();
2302         for (E e : c)
2303             list.add(e);
2304         return list;
2305     }
2306 
2307     static final class KeySet<E>
2308             extends AbstractSet<E> implements NavigableSet<E> {
2309         private final ConcurrentNavigableMap<E,?> m;
2310         KeySet(ConcurrentNavigableMap<E,?> map) { m = map; }
2311         public int size() { return m.size(); }
2312         public boolean isEmpty() { return m.isEmpty(); }
2313         public boolean contains(Object o) { return m.containsKey(o); }
2314         public boolean remove(Object o) { return m.remove(o) != null; }
2315         public void clear() { m.clear(); }
2316         public E lower(E e) { return m.lowerKey(e); }
2317         public E floor(E e) { return m.floorKey(e); }
2318         public E ceiling(E e) { return m.ceilingKey(e); }
2319         public E higher(E e) { return m.higherKey(e); }
2320         public Comparator<? super E> comparator() { return m.comparator(); }
2321         public E first() { return m.firstKey(); }
2322         public E last() { return m.lastKey(); }
2323         public E pollFirst() {
2324             Map.Entry<E,?> e = m.pollFirstEntry();
2325             return (e == null) ? null : e.getKey();
2326         }
2327         public E pollLast() {
2328             Map.Entry<E,?> e = m.pollLastEntry();
2329             return (e == null) ? null : e.getKey();
2330         }
2331         public Iterator<E> iterator() {
2332             if (m instanceof ConcurrentSkipListMap)
2333                 return ((ConcurrentSkipListMap<E,Object>)m).keyIterator();
2334             else
2335                 return ((ConcurrentSkipListMap.SubMap<E,Object>)m).keyIterator();
2336         }
2337         public boolean equals(Object o) {
2338             if (o == this)
2339                 return true;
2340             if (!(o instanceof Set))
2341                 return false;
2342             Collection<?> c = (Collection<?>) o;
2343             try {
2344                 return containsAll(c) && c.containsAll(this);
2345             } catch (ClassCastException unused)   {
2346                 return false;
2347             } catch (NullPointerException unused) {
2348                 return false;


2359                                       boolean toInclusive) {
2360             return new KeySet<E>(m.subMap(fromElement, fromInclusive,
2361                                           toElement,   toInclusive));
2362         }
2363         public NavigableSet<E> headSet(E toElement, boolean inclusive) {
2364             return new KeySet<E>(m.headMap(toElement, inclusive));
2365         }
2366         public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
2367             return new KeySet<E>(m.tailMap(fromElement, inclusive));
2368         }
2369         public NavigableSet<E> subSet(E fromElement, E toElement) {
2370             return subSet(fromElement, true, toElement, false);
2371         }
2372         public NavigableSet<E> headSet(E toElement) {
2373             return headSet(toElement, false);
2374         }
2375         public NavigableSet<E> tailSet(E fromElement) {
2376             return tailSet(fromElement, true);
2377         }
2378         public NavigableSet<E> descendingSet() {
2379             return new KeySet<E>(m.descendingMap());
2380         }
2381     }
2382 
2383     static final class Values<E> extends AbstractCollection<E> {
2384         private final ConcurrentNavigableMap<?, E> m;
2385         Values(ConcurrentNavigableMap<?, E> map) {
2386             m = map;
2387         }
2388         public Iterator<E> iterator() {
2389             if (m instanceof ConcurrentSkipListMap)
2390                 return ((ConcurrentSkipListMap<?,E>)m).valueIterator();
2391             else
2392                 return ((SubMap<?,E>)m).valueIterator();
2393         }
2394         public boolean isEmpty() {
2395             return m.isEmpty();
2396         }
2397         public int size() {
2398             return m.size();
2399         }
2400         public boolean contains(Object o) {
2401             return m.containsValue(o);
2402         }
2403         public void clear() {
2404             m.clear();
2405         }
2406         public Object[] toArray()     { return toList(this).toArray();  }
2407         public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
2408     }
2409 
2410     static final class EntrySet<K1,V1> extends AbstractSet<Map.Entry<K1,V1>> {
2411         private final ConcurrentNavigableMap<K1, V1> m;
2412         EntrySet(ConcurrentNavigableMap<K1, V1> map) {
2413             m = map;
2414         }
2415 
2416         public Iterator<Map.Entry<K1,V1>> iterator() {
2417             if (m instanceof ConcurrentSkipListMap)
2418                 return ((ConcurrentSkipListMap<K1,V1>)m).entryIterator();
2419             else
2420                 return ((SubMap<K1,V1>)m).entryIterator();
2421         }
2422 
2423         public boolean contains(Object o) {
2424             if (!(o instanceof Map.Entry))
2425                 return false;
2426             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
2427             V1 v = m.get(e.getKey());
2428             return v != null && v.equals(e.getValue());
2429         }
2430         public boolean remove(Object o) {
2431             if (!(o instanceof Map.Entry))
2432                 return false;
2433             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
2434             return m.remove(e.getKey(),
2435                             e.getValue());
2436         }
2437         public boolean isEmpty() {
2438             return m.isEmpty();
2439         }
2440         public int size() {
2441             return m.size();
2442         }
2443         public void clear() {
2444             m.clear();
2445         }
2446         public boolean equals(Object o) {
2447             if (o == this)
2448                 return true;
2449             if (!(o instanceof Set))
2450                 return false;
2451             Collection<?> c = (Collection<?>) o;
2452             try {
2453                 return containsAll(c) && c.containsAll(this);


2553                 return false;
2554             if (hi == null)
2555                 return true;
2556             K k = n.key;
2557             if (k == null) // pass by markers and headers
2558                 return true;
2559             int c = m.compare(k, hi);
2560             if (c > 0 || (c == 0 && !hiInclusive))
2561                 return false;
2562             return true;
2563         }
2564 
2565         /**
2566          * Returns lowest node. This node might not be in range, so
2567          * most usages need to check bounds
2568          */
2569         private ConcurrentSkipListMap.Node<K,V> loNode() {
2570             if (lo == null)
2571                 return m.findFirst();
2572             else if (loInclusive)
2573                 return m.findNear(lo, GT|EQ);
2574             else
2575                 return m.findNear(lo, GT);
2576         }
2577 
2578         /**
2579          * Returns highest node. This node might not be in range, so
2580          * most usages need to check bounds
2581          */
2582         private ConcurrentSkipListMap.Node<K,V> hiNode() {
2583             if (hi == null)
2584                 return m.findLast();
2585             else if (hiInclusive)
2586                 return m.findNear(hi, LT|EQ);
2587             else
2588                 return m.findNear(hi, LT);
2589         }
2590 
2591         /**
2592          * Returns lowest absolute key (ignoring directonality)
2593          */
2594         private K lowestKey() {
2595             ConcurrentSkipListMap.Node<K,V> n = loNode();
2596             if (isBeforeEnd(n))
2597                 return n.key;
2598             else
2599                 throw new NoSuchElementException();
2600         }
2601 
2602         /**
2603          * Returns highest absolute key (ignoring directonality)
2604          */
2605         private K highestKey() {
2606             ConcurrentSkipListMap.Node<K,V> n = hiNode();
2607             if (n != null) {
2608                 K last = n.key;


2650 
2651         private Map.Entry<K,V> removeHighest() {
2652             for (;;) {
2653                 Node<K,V> n = hiNode();
2654                 if (n == null)
2655                     return null;
2656                 K k = n.key;
2657                 if (!inBounds(k))
2658                     return null;
2659                 V v = m.doRemove(k, null);
2660                 if (v != null)
2661                     return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2662             }
2663         }
2664 
2665         /**
2666          * Submap version of ConcurrentSkipListMap.getNearEntry
2667          */
2668         private Map.Entry<K,V> getNearEntry(K key, int rel) {
2669             if (isDescending) { // adjust relation for direction
2670                 if ((rel & LT) == 0)
2671                     rel |= LT;
2672                 else
2673                     rel &= ~LT;
2674             }
2675             if (tooLow(key))
2676                 return ((rel & LT) != 0) ? null : lowestEntry();
2677             if (tooHigh(key))
2678                 return ((rel & LT) != 0) ? highestEntry() : null;
2679             for (;;) {
2680                 Node<K,V> n = m.findNear(key, rel);
2681                 if (n == null || !inBounds(n.key))
2682                     return null;
2683                 K k = n.key;
2684                 V v = n.getValidValue();
2685                 if (v != null)
2686                     return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2687             }
2688         }
2689 
2690         // Almost the same as getNearEntry, except for keys
2691         private K getNearKey(K key, int rel) {
2692             if (isDescending) { // adjust relation for direction
2693                 if ((rel & LT) == 0)
2694                     rel |= LT;
2695                 else
2696                     rel &= ~LT;
2697             }
2698             if (tooLow(key)) {
2699                 if ((rel & LT) == 0) {
2700                     ConcurrentSkipListMap.Node<K,V> n = loNode();
2701                     if (isBeforeEnd(n))
2702                         return n.key;
2703                 }
2704                 return null;
2705             }
2706             if (tooHigh(key)) {
2707                 if ((rel & LT) != 0) {
2708                     ConcurrentSkipListMap.Node<K,V> n = hiNode();
2709                     if (n != null) {
2710                         K last = n.key;
2711                         if (inBounds(last))
2712                             return last;
2713                     }
2714                 }
2715                 return null;
2716             }
2717             for (;;) {
2718                 Node<K,V> n = m.findNear(key, rel);
2719                 if (n == null || !inBounds(n.key))
2720                     return null;
2721                 K k = n.key;
2722                 V v = n.getValidValue();
2723                 if (v != null)
2724                     return k;
2725             }
2726         }
2727 
2728         /* ----------------  Map API methods -------------- */
2729 
2730         public boolean containsKey(Object key) {
2731             if (key == null) throw new NullPointerException();
2732             K k = (K)key;
2733             return inBounds(k) && m.containsKey(k);
2734         }
2735 
2736         public V get(Object key) {
2737             if (key == null) throw new NullPointerException();
2738             K k = (K)key;
2739             return (!inBounds(k)) ? null : m.get(k);
2740         }
2741 
2742         public V put(K key, V value) {
2743             checkKeyBounds(key);
2744             return m.put(key, value);
2745         }
2746 
2747         public V remove(Object key) {
2748             K k = (K)key;
2749             return (!inBounds(k)) ? null : m.remove(k);
2750         }
2751 
2752         public int size() {
2753             long count = 0;
2754             for (ConcurrentSkipListMap.Node<K,V> n = loNode();
2755                  isBeforeEnd(n);
2756                  n = n.next) {
2757                 if (n.getValidValue() != null)
2758                     ++count;
2759             }


2886         public SubMap<K,V> subMap(K fromKey, K toKey) {
2887             return subMap(fromKey, true, toKey, false);
2888         }
2889 
2890         public SubMap<K,V> headMap(K toKey) {
2891             return headMap(toKey, false);
2892         }
2893 
2894         public SubMap<K,V> tailMap(K fromKey) {
2895             return tailMap(fromKey, true);
2896         }
2897 
2898         public SubMap<K,V> descendingMap() {
2899             return new SubMap<K,V>(m, lo, loInclusive,
2900                                    hi, hiInclusive, !isDescending);
2901         }
2902 
2903         /* ----------------  Relational methods -------------- */
2904 
2905         public Map.Entry<K,V> ceilingEntry(K key) {
2906             return getNearEntry(key, GT|EQ);
2907         }
2908 
2909         public K ceilingKey(K key) {
2910             return getNearKey(key, GT|EQ);
2911         }
2912 
2913         public Map.Entry<K,V> lowerEntry(K key) {
2914             return getNearEntry(key, LT);
2915         }
2916 
2917         public K lowerKey(K key) {
2918             return getNearKey(key, LT);
2919         }
2920 
2921         public Map.Entry<K,V> floorEntry(K key) {
2922             return getNearEntry(key, LT|EQ);
2923         }
2924 
2925         public K floorKey(K key) {
2926             return getNearKey(key, LT|EQ);
2927         }
2928 
2929         public Map.Entry<K,V> higherEntry(K key) {
2930             return getNearEntry(key, GT);
2931         }
2932 
2933         public K higherKey(K key) {
2934             return getNearKey(key, GT);
2935         }
2936 
2937         public K firstKey() {
2938             return isDescending ? highestKey() : lowestKey();
2939         }
2940 
2941         public K lastKey() {
2942             return isDescending ? lowestKey() : highestKey();
2943         }
2944 
2945         public Map.Entry<K,V> firstEntry() {
2946             return isDescending ? highestEntry() : lowestEntry();
2947         }
2948 
2949         public Map.Entry<K,V> lastEntry() {
2950             return isDescending ? lowestEntry() : highestEntry();
2951         }
2952 
2953         public Map.Entry<K,V> pollFirstEntry() {
2954             return isDescending ? removeHighest() : removeLowest();
2955         }
2956 
2957         public Map.Entry<K,V> pollLastEntry() {
2958             return isDescending ? removeLowest() : removeHighest();
2959         }
2960 
2961         /* ---------------- Submap Views -------------- */
2962 
2963         public NavigableSet<K> keySet() {
2964             KeySet<K> ks = keySetView;
2965             return (ks != null) ? ks : (keySetView = new KeySet<K>(this));
2966         }
2967 
2968         public NavigableSet<K> navigableKeySet() {
2969             KeySet<K> ks = keySetView;
2970             return (ks != null) ? ks : (keySetView = new KeySet<K>(this));
2971         }
2972 
2973         public Collection<V> values() {
2974             Collection<V> vs = valuesView;
2975             return (vs != null) ? vs : (valuesView = new Values<V>(this));
2976         }
2977 
2978         public Set<Map.Entry<K,V>> entrySet() {
2979             Set<Map.Entry<K,V>> es = entrySetView;
2980             return (es != null) ? es : (entrySetView = new EntrySet<K,V>(this));
2981         }
2982 
2983         public NavigableSet<K> descendingKeySet() {
2984             return descendingMap().navigableKeySet();
2985         }
2986 
2987         Iterator<K> keyIterator() {
2988             return new SubMapKeyIterator();
2989         }
2990 
2991         Iterator<V> valueIterator() {
2992             return new SubMapValueIterator();
2993         }
2994 
2995         Iterator<Map.Entry<K,V>> entryIterator() {
2996             return new SubMapEntryIterator();
2997         }
2998 
2999         /**
3000          * Variant of main Iter class to traverse through submaps.


3094                 return n.key;
3095             }
3096         }
3097 
3098         final class SubMapEntryIterator extends SubMapIter<Map.Entry<K,V>> {
3099             public Map.Entry<K,V> next() {
3100                 Node<K,V> n = next;
3101                 V v = nextValue;
3102                 advance();
3103                 return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
3104             }
3105         }
3106     }
3107 
3108     // Unsafe mechanics
3109     private static final sun.misc.Unsafe UNSAFE;
3110     private static final long headOffset;
3111     static {
3112         try {
3113             UNSAFE = sun.misc.Unsafe.getUnsafe();
3114             Class<?> k = ConcurrentSkipListMap.class;
3115             headOffset = UNSAFE.objectFieldOffset
3116                 (k.getDeclaredField("head"));
3117         } catch (Exception e) {
3118             throw new Error(e);
3119         }
3120     }
3121 }