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

Print this page




 357     /** Lazily initialized values collection */
 358     private transient Values values;
 359     /** Lazily initialized descending key set */
 360     private transient ConcurrentNavigableMap<K,V> descendingMap;
 361 
 362     /**
 363      * Initializes or resets state. Needed by constructors, clone,
 364      * clear, readObject. and ConcurrentSkipListSet.clone.
 365      * (Note that comparator must be separately initialized.)
 366      */
 367     final void initialize() {
 368         keySet = null;
 369         entrySet = null;
 370         values = null;
 371         descendingMap = null;
 372         randomSeed = seedGenerator.nextInt() | 0x0100; // ensure nonzero
 373         head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),
 374                                   null, null, 1);
 375     }
 376 
 377     /** Updater for casHead */
 378     private static final
 379         AtomicReferenceFieldUpdater<ConcurrentSkipListMap, HeadIndex>
 380         headUpdater = AtomicReferenceFieldUpdater.newUpdater
 381         (ConcurrentSkipListMap.class, HeadIndex.class, "head");
 382 
 383     /**
 384      * compareAndSet head node
 385      */
 386     private boolean casHead(HeadIndex<K,V> cmp, HeadIndex<K,V> val) {
 387         return headUpdater.compareAndSet(this, cmp, val);
 388     }
 389 
 390     /* ---------------- Nodes -------------- */
 391 
 392     /**
 393      * Nodes hold keys and values, and are singly linked in sorted
 394      * order, possibly with some intervening marker nodes. The list is
 395      * headed by a dummy node accessible as head.node. The value field
 396      * is declared only as Object because it takes special non-V
 397      * values for marker and header nodes.
 398      */
 399     static final class Node<K,V> {
 400         final K key;
 401         volatile Object value;
 402         volatile Node<K,V> next;
 403 
 404         /**
 405          * Creates a new regular node.
 406          */
 407         Node(K key, Object value, Node<K,V> next) {
 408             this.key = key;
 409             this.value = value;
 410             this.next = next;
 411         }
 412 
 413         /**
 414          * Creates a new marker node. A marker is distinguished by
 415          * having its value field point to itself.  Marker nodes also
 416          * have null keys, a fact that is exploited in a few places,
 417          * but this doesn't distinguish markers from the base-level
 418          * header node (head.node), which also has a null key.
 419          */
 420         Node(Node<K,V> next) {
 421             this.key = null;
 422             this.value = this;
 423             this.next = next;
 424         }
 425 
 426         /** Updater for casNext */
 427         static final AtomicReferenceFieldUpdater<Node, Node>
 428             nextUpdater = AtomicReferenceFieldUpdater.newUpdater
 429             (Node.class, Node.class, "next");
 430 
 431         /** Updater for casValue */
 432         static final AtomicReferenceFieldUpdater<Node, Object>
 433             valueUpdater = AtomicReferenceFieldUpdater.newUpdater
 434             (Node.class, Object.class, "value");
 435 
 436         /**
 437          * compareAndSet value field
 438          */
 439         boolean casValue(Object cmp, Object val) {
 440             return valueUpdater.compareAndSet(this, cmp, val);
 441         }
 442 
 443         /**
 444          * compareAndSet next field
 445          */
 446         boolean casNext(Node<K,V> cmp, Node<K,V> val) {
 447             return nextUpdater.compareAndSet(this, cmp, val);
 448         }
 449 
 450         /**
 451          * Returns true if this node is a marker. This method isn't
 452          * actually called in any current code checking for markers
 453          * because callers will have already read value field and need
 454          * to use that read (not another done here) and so directly
 455          * test if value points to node.
 456          * @param n a possibly null reference to a node
 457          * @return true if this node is a marker node
 458          */
 459         boolean isMarker() {
 460             return value == this;
 461         }
 462 
 463         /**
 464          * Returns true if this node is the header of base-level list.
 465          * @return true if this node is header node
 466          */
 467         boolean isBaseHeader() {


 505          * is deleted, else null.
 506          */
 507         V getValidValue() {
 508             Object v = value;
 509             if (v == this || v == BASE_HEADER)
 510                 return null;
 511             return (V)v;
 512         }
 513 
 514         /**
 515          * Creates and returns a new SimpleImmutableEntry holding current
 516          * mapping if this node holds a valid value, else null.
 517          * @return new entry or null
 518          */
 519         AbstractMap.SimpleImmutableEntry<K,V> createSnapshot() {
 520             V v = getValidValue();
 521             if (v == null)
 522                 return null;
 523             return new AbstractMap.SimpleImmutableEntry<K,V>(key, v);
 524         }








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






 594     }
 595 
 596     /* ---------------- Head nodes -------------- */
 597 
 598     /**
 599      * Nodes heading each level keep track of their level.
 600      */
 601     static final class HeadIndex<K,V> extends Index<K,V> {
 602         final int level;
 603         HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {
 604             super(node, down, right);
 605             this.level = level;
 606         }
 607     }
 608 
 609     /* ---------------- Comparison utilities -------------- */
 610 
 611     /**
 612      * Represents a key with a comparator as a Comparable.
 613      *


 623      * Comparators vs Comparables, which seems like the right
 624      * tradeoff.
 625      */
 626     static final class ComparableUsingComparator<K> implements Comparable<K> {
 627         final K actualKey;
 628         final Comparator<? super K> cmp;
 629         ComparableUsingComparator(K key, Comparator<? super K> cmp) {
 630             this.actualKey = key;
 631             this.cmp = cmp;
 632         }
 633         public int compareTo(K k2) {
 634             return cmp.compare(actualKey, k2);
 635         }
 636     }
 637 
 638     /**
 639      * If using comparator, return a ComparableUsingComparator, else
 640      * cast key as Comparable, which may cause ClassCastException,
 641      * which is propagated back to caller.
 642      */
 643     private Comparable<? super K> comparable(Object key) throws ClassCastException {

 644         if (key == null)
 645             throw new NullPointerException();
 646         if (comparator != null)
 647             return new ComparableUsingComparator<K>((K)key, comparator);
 648         else
 649             return (Comparable<? super K>)key;
 650     }
 651 
 652     /**
 653      * Compares using comparator or natural ordering. Used when the
 654      * ComparableUsingComparator approach doesn't apply.
 655      */
 656     int compare(K k1, K k2) throws ClassCastException {
 657         Comparator<? super K> cmp = comparator;
 658         if (cmp != null)
 659             return cmp.compare(k1, k2);
 660         else
 661             return ((Comparable<? super K>)k1).compareTo(k2);
 662     }
 663 


 811      * @return the value, or null if absent
 812      */
 813     private V doGet(Object okey) {
 814         Comparable<? super K> key = comparable(okey);
 815         Node<K,V> bound = null;
 816         Index<K,V> q = head;
 817         Index<K,V> r = q.right;
 818         Node<K,V> n;
 819         K k;
 820         int c;
 821         for (;;) {
 822             Index<K,V> d;
 823             // Traverse rights
 824             if (r != null && (n = r.node) != bound && (k = n.key) != null) {
 825                 if ((c = key.compareTo(k)) > 0) {
 826                     q = r;
 827                     r = r.right;
 828                     continue;
 829                 } else if (c == 0) {
 830                     Object v = n.value;
 831                     return (v != null)? (V)v : getUsingFindNode(key);
 832                 } else
 833                     bound = n;
 834             }
 835 
 836             // Traverse down
 837             if ((d = q.down) != null) {
 838                 q = d;
 839                 r = d.right;
 840             } else
 841                 break;
 842         }
 843 
 844         // Traverse nexts
 845         for (n = q.node.next;  n != null; n = n.next) {
 846             if ((k = n.key) != null) {
 847                 if ((c = key.compareTo(k)) == 0) {
 848                     Object v = n.value;
 849                     return (v != null)? (V)v : getUsingFindNode(key);
 850                 } else if (c < 0)
 851                     break;
 852             }
 853         }
 854         return null;
 855     }
 856 
 857     /**
 858      * Performs map.get via findNode.  Used as a backup if doGet
 859      * encounters an in-progress deletion.
 860      * @param key the key
 861      * @return the value, or null if absent
 862      */
 863     private V getUsingFindNode(Comparable<? super K> key) {
 864         /*
 865          * Loop needed here and elsewhere in case value field goes
 866          * null just as it is about to be returned, in which case we
 867          * lost a race with a deletion, so must retry.
 868          */
 869         for (;;) {


 926                     insertIndex(z, level);
 927                 return null;
 928             }
 929         }
 930     }
 931 
 932     /**
 933      * Returns a random level for inserting a new node.
 934      * Hardwired to k=1, p=0.5, max 31 (see above and
 935      * Pugh's "Skip List Cookbook", sec 3.4).
 936      *
 937      * This uses the simplest of the generators described in George
 938      * Marsaglia's "Xorshift RNGs" paper.  This is not a high-quality
 939      * generator but is acceptable here.
 940      */
 941     private int randomLevel() {
 942         int x = randomSeed;
 943         x ^= x << 13;
 944         x ^= x >>> 17;
 945         randomSeed = x ^= x << 5;
 946         if ((x & 0x8001) != 0) // test highest and lowest bits
 947             return 0;
 948         int level = 1;
 949         while (((x >>>= 1) & 1) != 0) ++level;
 950         return level;
 951     }
 952 
 953     /**
 954      * Creates and adds index nodes for the given node.
 955      * @param z the node
 956      * @param level the level of the index
 957      */
 958     private void insertIndex(Node<K,V> z, int level) {
 959         HeadIndex<K,V> h = head;
 960         int max = h.level;
 961 
 962         if (level <= max) {
 963             Index<K,V> idx = null;
 964             for (int i = 1; i <= level; ++i)
 965                 idx = new Index<K,V>(z, idx, null);
 966             addIndex(idx, h, level);


1239          * because this doesn't use comparisons.  So traversals of
1240          * both levels are folded together.
1241          */
1242         Index<K,V> q = head;
1243         for (;;) {
1244             Index<K,V> d, r;
1245             if ((r = q.right) != null) {
1246                 if (r.indexesDeletedNode()) {
1247                     q.unlink(r);
1248                     q = head; // restart
1249                 }
1250                 else
1251                     q = r;
1252             } else if ((d = q.down) != null) {
1253                 q = d;
1254             } else {
1255                 Node<K,V> b = q.node;
1256                 Node<K,V> n = b.next;
1257                 for (;;) {
1258                     if (n == null)
1259                         return (b.isBaseHeader())? null : b;
1260                     Node<K,V> f = n.next;            // inconsistent read
1261                     if (n != b.next)
1262                         break;
1263                     Object v = n.value;
1264                     if (v == null) {                 // n is deleted
1265                         n.helpDelete(b, f);
1266                         break;
1267                     }
1268                     if (v == n || b.value == null)   // b is deleted
1269                         break;
1270                     b = n;
1271                     n = f;
1272                 }
1273                 q = head; // restart
1274             }
1275         }
1276     }
1277 
1278     /**
1279      * Specialized variant of findPredecessor to get predecessor of last


1357 
1358     // Control values OR'ed as arguments to findNear
1359 
1360     private static final int EQ = 1;
1361     private static final int LT = 2;
1362     private static final int GT = 0; // Actually checked as !LT
1363 
1364     /**
1365      * Utility for ceiling, floor, lower, higher methods.
1366      * @param kkey the key
1367      * @param rel the relation -- OR'ed combination of EQ, LT, GT
1368      * @return nearest node fitting relation, or null if no such
1369      */
1370     Node<K,V> findNear(K kkey, int rel) {
1371         Comparable<? super K> key = comparable(kkey);
1372         for (;;) {
1373             Node<K,V> b = findPredecessor(key);
1374             Node<K,V> n = b.next;
1375             for (;;) {
1376                 if (n == null)
1377                     return ((rel & LT) == 0 || b.isBaseHeader())? null : b;
1378                 Node<K,V> f = n.next;
1379                 if (n != b.next)                  // inconsistent read
1380                     break;
1381                 Object v = n.value;
1382                 if (v == null) {                  // n is deleted
1383                     n.helpDelete(b, f);
1384                     break;
1385                 }
1386                 if (v == n || b.value == null)    // b is deleted
1387                     break;
1388                 int c = key.compareTo(n.key);
1389                 if ((c == 0 && (rel & EQ) != 0) ||
1390                     (c <  0 && (rel & LT) == 0))
1391                     return n;
1392                 if ( c <= 0 && (rel & LT) != 0)
1393                     return (b.isBaseHeader())? null : b;
1394                 b = n;
1395                 n = f;
1396             }
1397         }
1398     }
1399 
1400     /**
1401      * Returns SimpleImmutableEntry for results of findNear.
1402      * @param key the key
1403      * @param rel the relation -- OR'ed combination of EQ, LT, GT
1404      * @return Entry fitting relation, or null if no such
1405      */
1406     AbstractMap.SimpleImmutableEntry<K,V> getNear(K key, int rel) {
1407         for (;;) {
1408             Node<K,V> n = findNear(key, rel);
1409             if (n == null)
1410                 return null;
1411             AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
1412             if (e != null)
1413                 return e;


1727      * contains more than <tt>Integer.MAX_VALUE</tt> elements, it
1728      * returns <tt>Integer.MAX_VALUE</tt>.
1729      *
1730      * <p>Beware that, unlike in most collections, this method is
1731      * <em>NOT</em> a constant-time operation. Because of the
1732      * asynchronous nature of these maps, determining the current
1733      * number of elements requires traversing them all to count them.
1734      * Additionally, it is possible for the size to change during
1735      * execution of this method, in which case the returned result
1736      * will be inaccurate. Thus, this method is typically not very
1737      * useful in concurrent applications.
1738      *
1739      * @return the number of elements in this map
1740      */
1741     public int size() {
1742         long count = 0;
1743         for (Node<K,V> n = findFirst(); n != null; n = n.next) {
1744             if (n.getValidValue() != null)
1745                 ++count;
1746         }
1747         return (count >= Integer.MAX_VALUE)? Integer.MAX_VALUE : (int)count;
1748     }
1749 
1750     /**
1751      * Returns <tt>true</tt> if this map contains no key-value mappings.
1752      * @return <tt>true</tt> if this map contains no key-value mappings
1753      */
1754     public boolean isEmpty() {
1755         return findFirst() == null;
1756     }
1757 
1758     /**
1759      * Removes all of the mappings from this map.
1760      */
1761     public void clear() {
1762         initialize();
1763     }
1764 
1765     /* ---------------- View methods -------------- */
1766 
1767     /*


2082 
2083     /**
2084      * Returns a key-value mapping associated with the greatest key
2085      * strictly less than the given key, or <tt>null</tt> if there is
2086      * no such key. The returned entry does <em>not</em> support the
2087      * <tt>Entry.setValue</tt> method.
2088      *
2089      * @throws ClassCastException {@inheritDoc}
2090      * @throws NullPointerException if the specified key is null
2091      */
2092     public Map.Entry<K,V> lowerEntry(K key) {
2093         return getNear(key, LT);
2094     }
2095 
2096     /**
2097      * @throws ClassCastException {@inheritDoc}
2098      * @throws NullPointerException if the specified key is null
2099      */
2100     public K lowerKey(K key) {
2101         Node<K,V> n = findNear(key, LT);
2102         return (n == null)? null : n.key;
2103     }
2104 
2105     /**
2106      * Returns a key-value mapping associated with the greatest key
2107      * less than or equal to the given key, or <tt>null</tt> if there
2108      * is no such key. The returned entry does <em>not</em> support
2109      * the <tt>Entry.setValue</tt> method.
2110      *
2111      * @param key the key
2112      * @throws ClassCastException {@inheritDoc}
2113      * @throws NullPointerException if the specified key is null
2114      */
2115     public Map.Entry<K,V> floorEntry(K key) {
2116         return getNear(key, LT|EQ);
2117     }
2118 
2119     /**
2120      * @param key the key
2121      * @throws ClassCastException {@inheritDoc}
2122      * @throws NullPointerException if the specified key is null
2123      */
2124     public K floorKey(K key) {
2125         Node<K,V> n = findNear(key, LT|EQ);
2126         return (n == null)? null : n.key;
2127     }
2128 
2129     /**
2130      * Returns a key-value mapping associated with the least key
2131      * greater than or equal to the given key, or <tt>null</tt> if
2132      * there is no such entry. The returned entry does <em>not</em>
2133      * support the <tt>Entry.setValue</tt> method.
2134      *
2135      * @throws ClassCastException {@inheritDoc}
2136      * @throws NullPointerException if the specified key is null
2137      */
2138     public Map.Entry<K,V> ceilingEntry(K key) {
2139         return getNear(key, GT|EQ);
2140     }
2141 
2142     /**
2143      * @throws ClassCastException {@inheritDoc}
2144      * @throws NullPointerException if the specified key is null
2145      */
2146     public K ceilingKey(K key) {
2147         Node<K,V> n = findNear(key, GT|EQ);
2148         return (n == null)? null : n.key;
2149     }
2150 
2151     /**
2152      * Returns a key-value mapping associated with the least key
2153      * strictly greater than the given key, or <tt>null</tt> if there
2154      * is no such key. The returned entry does <em>not</em> support
2155      * the <tt>Entry.setValue</tt> method.
2156      *
2157      * @param key the key
2158      * @throws ClassCastException {@inheritDoc}
2159      * @throws NullPointerException if the specified key is null
2160      */
2161     public Map.Entry<K,V> higherEntry(K key) {
2162         return getNear(key, GT);
2163     }
2164 
2165     /**
2166      * @param key the key
2167      * @throws ClassCastException {@inheritDoc}
2168      * @throws NullPointerException if the specified key is null
2169      */
2170     public K higherKey(K key) {
2171         Node<K,V> n = findNear(key, GT);
2172         return (n == null)? null : n.key;
2173     }
2174 
2175     /**
2176      * Returns a key-value mapping associated with the least
2177      * key in this map, or <tt>null</tt> if the map is empty.
2178      * The returned entry does <em>not</em> support
2179      * the <tt>Entry.setValue</tt> method.
2180      */
2181     public Map.Entry<K,V> firstEntry() {
2182         for (;;) {
2183             Node<K,V> n = findFirst();
2184             if (n == null)
2185                 return null;
2186             AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
2187             if (e != null)
2188                 return e;
2189         }
2190     }
2191 
2192     /**


2325     Iterator<Map.Entry<K,V>> entryIterator() {
2326         return new EntryIterator();
2327     }
2328 
2329     /* ---------------- View Classes -------------- */
2330 
2331     /*
2332      * View classes are static, delegating to a ConcurrentNavigableMap
2333      * to allow use by SubMaps, which outweighs the ugliness of
2334      * needing type-tests for Iterator methods.
2335      */
2336 
2337     static final <E> List<E> toList(Collection<E> c) {
2338         // Using size() here would be a pessimization.
2339         List<E> list = new ArrayList<E>();
2340         for (E e : c)
2341             list.add(e);
2342         return list;
2343     }
2344 
2345     static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {

2346         private final ConcurrentNavigableMap<E,Object> m;
2347         KeySet(ConcurrentNavigableMap<E,Object> map) { m = map; }
2348         public int size() { return m.size(); }
2349         public boolean isEmpty() { return m.isEmpty(); }
2350         public boolean contains(Object o) { return m.containsKey(o); }
2351         public boolean remove(Object o) { return m.remove(o) != null; }
2352         public void clear() { m.clear(); }
2353         public E lower(E e) { return m.lowerKey(e); }
2354         public E floor(E e) { return m.floorKey(e); }
2355         public E ceiling(E e) { return m.ceilingKey(e); }
2356         public E higher(E e) { return m.higherKey(e); }
2357         public Comparator<? super E> comparator() { return m.comparator(); }
2358         public E first() { return m.firstKey(); }
2359         public E last() { return m.lastKey(); }
2360         public E pollFirst() {
2361             Map.Entry<E,Object> e = m.pollFirstEntry();
2362             return e == null? null : e.getKey();
2363         }
2364         public E pollLast() {
2365             Map.Entry<E,Object> e = m.pollLastEntry();
2366             return e == null? null : e.getKey();
2367         }
2368         public Iterator<E> iterator() {
2369             if (m instanceof ConcurrentSkipListMap)
2370                 return ((ConcurrentSkipListMap<E,Object>)m).keyIterator();
2371             else
2372                 return ((ConcurrentSkipListMap.SubMap<E,Object>)m).keyIterator();
2373         }
2374         public boolean equals(Object o) {
2375             if (o == this)
2376                 return true;
2377             if (!(o instanceof Set))
2378                 return false;
2379             Collection<?> c = (Collection<?>) o;
2380             try {
2381                 return containsAll(c) && c.containsAll(this);
2382             } catch (ClassCastException unused)   {
2383                 return false;
2384             } catch (NullPointerException unused) {
2385                 return false;
2386             }


2693                 K k = n.key;
2694                 if (!inBounds(k))
2695                     return null;
2696                 V v = m.doRemove(k, null);
2697                 if (v != null)
2698                     return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2699             }
2700         }
2701 
2702         /**
2703          * Submap version of ConcurrentSkipListMap.getNearEntry
2704          */
2705         private Map.Entry<K,V> getNearEntry(K key, int rel) {
2706             if (isDescending) { // adjust relation for direction
2707                 if ((rel & m.LT) == 0)
2708                     rel |= m.LT;
2709                 else
2710                     rel &= ~m.LT;
2711             }
2712             if (tooLow(key))
2713                 return ((rel & m.LT) != 0)? null : lowestEntry();
2714             if (tooHigh(key))
2715                 return ((rel & m.LT) != 0)? highestEntry() : null;
2716             for (;;) {
2717                 Node<K,V> n = m.findNear(key, rel);
2718                 if (n == null || !inBounds(n.key))
2719                     return null;
2720                 K k = n.key;
2721                 V v = n.getValidValue();
2722                 if (v != null)
2723                     return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2724             }
2725         }
2726 
2727         // Almost the same as getNearEntry, except for keys
2728         private K getNearKey(K key, int rel) {
2729             if (isDescending) { // adjust relation for direction
2730                 if ((rel & m.LT) == 0)
2731                     rel |= m.LT;
2732                 else
2733                     rel &= ~m.LT;
2734             }
2735             if (tooLow(key)) {


2766 
2767         public boolean containsKey(Object key) {
2768             if (key == null) throw new NullPointerException();
2769             K k = (K)key;
2770             return inBounds(k) && m.containsKey(k);
2771         }
2772 
2773         public V get(Object key) {
2774             if (key == null) throw new NullPointerException();
2775             K k = (K)key;
2776             return ((!inBounds(k)) ? null : m.get(k));
2777         }
2778 
2779         public V put(K key, V value) {
2780             checkKeyBounds(key);
2781             return m.put(key, value);
2782         }
2783 
2784         public V remove(Object key) {
2785             K k = (K)key;
2786             return (!inBounds(k))? null : m.remove(k);
2787         }
2788 
2789         public int size() {
2790             long count = 0;
2791             for (ConcurrentSkipListMap.Node<K,V> n = loNode();
2792                  isBeforeEnd(n);
2793                  n = n.next) {
2794                 if (n.getValidValue() != null)
2795                     ++count;
2796             }
2797             return count >= Integer.MAX_VALUE? Integer.MAX_VALUE : (int)count;
2798         }
2799 
2800         public boolean isEmpty() {
2801             return !isBeforeEnd(loNode());
2802         }
2803 
2804         public boolean containsValue(Object value) {
2805             if (value == null)
2806                 throw new NullPointerException();
2807             for (ConcurrentSkipListMap.Node<K,V> n = loNode();
2808                  isBeforeEnd(n);
2809                  n = n.next) {
2810                 V v = n.getValidValue();
2811                 if (v != null && value.equals(v))
2812                     return true;
2813             }
2814             return false;
2815         }
2816 
2817         public void clear() {


2955             return getNearKey(key, (m.LT));
2956         }
2957 
2958         public Map.Entry<K,V> floorEntry(K key) {
2959             return getNearEntry(key, (m.LT|m.EQ));
2960         }
2961 
2962         public K floorKey(K key) {
2963             return getNearKey(key, (m.LT|m.EQ));
2964         }
2965 
2966         public Map.Entry<K,V> higherEntry(K key) {
2967             return getNearEntry(key, (m.GT));
2968         }
2969 
2970         public K higherKey(K key) {
2971             return getNearKey(key, (m.GT));
2972         }
2973 
2974         public K firstKey() {
2975             return isDescending? highestKey() : lowestKey();
2976         }
2977 
2978         public K lastKey() {
2979             return isDescending? lowestKey() : highestKey();
2980         }
2981 
2982         public Map.Entry<K,V> firstEntry() {
2983             return isDescending? highestEntry() : lowestEntry();
2984         }
2985 
2986         public Map.Entry<K,V> lastEntry() {
2987             return isDescending? lowestEntry() : highestEntry();
2988         }
2989 
2990         public Map.Entry<K,V> pollFirstEntry() {
2991             return isDescending? removeHighest() : removeLowest();
2992         }
2993 
2994         public Map.Entry<K,V> pollLastEntry() {
2995             return isDescending? removeLowest() : removeHighest();
2996         }
2997 
2998         /* ---------------- Submap Views -------------- */
2999 
3000         public NavigableSet<K> keySet() {
3001             KeySet<K> ks = keySetView;
3002             return (ks != null) ? ks : (keySetView = new KeySet(this));
3003         }
3004 
3005         public NavigableSet<K> navigableKeySet() {
3006             KeySet<K> ks = keySetView;
3007             return (ks != null) ? ks : (keySetView = new KeySet(this));
3008         }
3009 
3010         public Collection<V> values() {
3011             Collection<V> vs = valuesView;
3012             return (vs != null) ? vs : (valuesView = new Values(this));
3013         }
3014 
3015         public Set<Map.Entry<K,V>> entrySet() {


3124             }
3125         }
3126 
3127         final class SubMapKeyIterator extends SubMapIter<K> {
3128             public K next() {
3129                 Node<K,V> n = next;
3130                 advance();
3131                 return n.key;
3132             }
3133         }
3134 
3135         final class SubMapEntryIterator extends SubMapIter<Map.Entry<K,V>> {
3136             public Map.Entry<K,V> next() {
3137                 Node<K,V> n = next;
3138                 V v = nextValue;
3139                 advance();
3140                 return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
3141             }
3142         }
3143     }


















3144 }


 357     /** Lazily initialized values collection */
 358     private transient Values values;
 359     /** Lazily initialized descending key set */
 360     private transient ConcurrentNavigableMap<K,V> descendingMap;
 361 
 362     /**
 363      * Initializes or resets state. Needed by constructors, clone,
 364      * clear, readObject. and ConcurrentSkipListSet.clone.
 365      * (Note that comparator must be separately initialized.)
 366      */
 367     final void initialize() {
 368         keySet = null;
 369         entrySet = null;
 370         values = null;
 371         descendingMap = null;
 372         randomSeed = seedGenerator.nextInt() | 0x0100; // ensure nonzero
 373         head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),
 374                                   null, null, 1);
 375     }
 376 






 377     /**
 378      * compareAndSet head node
 379      */
 380     private boolean casHead(HeadIndex<K,V> cmp, HeadIndex<K,V> val) {
 381         return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val);
 382     }
 383 
 384     /* ---------------- Nodes -------------- */
 385 
 386     /**
 387      * Nodes hold keys and values, and are singly linked in sorted
 388      * order, possibly with some intervening marker nodes. The list is
 389      * headed by a dummy node accessible as head.node. The value field
 390      * is declared only as Object because it takes special non-V
 391      * values for marker and header nodes.
 392      */
 393     static final class Node<K,V> {
 394         final K key;
 395         volatile Object value;
 396         volatile Node<K,V> next;
 397 
 398         /**
 399          * Creates a new regular node.
 400          */
 401         Node(K key, Object value, Node<K,V> next) {
 402             this.key = key;
 403             this.value = value;
 404             this.next = next;
 405         }
 406 
 407         /**
 408          * Creates a new marker node. A marker is distinguished by
 409          * having its value field point to itself.  Marker nodes also
 410          * have null keys, a fact that is exploited in a few places,
 411          * but this doesn't distinguish markers from the base-level
 412          * header node (head.node), which also has a null key.
 413          */
 414         Node(Node<K,V> next) {
 415             this.key = null;
 416             this.value = this;
 417             this.next = next;
 418         }
 419 










 420         /**
 421          * compareAndSet value field
 422          */
 423         boolean casValue(Object cmp, Object val) {
 424             return UNSAFE.compareAndSwapObject(this, valueOffset, cmp, val);
 425         }
 426 
 427         /**
 428          * compareAndSet next field
 429          */
 430         boolean casNext(Node<K,V> cmp, Node<K,V> val) {
 431             return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
 432         }
 433 
 434         /**
 435          * Returns true if this node is a marker. This method isn't
 436          * actually called in any current code checking for markers
 437          * because callers will have already read value field and need
 438          * to use that read (not another done here) and so directly
 439          * test if value points to node.
 440          * @param n a possibly null reference to a node
 441          * @return true if this node is a marker node
 442          */
 443         boolean isMarker() {
 444             return value == this;
 445         }
 446 
 447         /**
 448          * Returns true if this node is the header of base-level list.
 449          * @return true if this node is header node
 450          */
 451         boolean isBaseHeader() {


 489          * is deleted, else null.
 490          */
 491         V getValidValue() {
 492             Object v = value;
 493             if (v == this || v == BASE_HEADER)
 494                 return null;
 495             return (V)v;
 496         }
 497 
 498         /**
 499          * Creates and returns a new SimpleImmutableEntry holding current
 500          * mapping if this node holds a valid value, else null.
 501          * @return new entry or null
 502          */
 503         AbstractMap.SimpleImmutableEntry<K,V> createSnapshot() {
 504             V v = getValidValue();
 505             if (v == null)
 506                 return null;
 507             return new AbstractMap.SimpleImmutableEntry<K,V>(key, v);
 508         }
 509 
 510         // Unsafe mechanics
 511         private static final sun.misc.Unsafe UNSAFE = sun.misc.Unsafe.getUnsafe();
 512         private static final long valueOffset =
 513             objectFieldOffset(UNSAFE, "value", Node.class);
 514         private static final long nextOffset =
 515             objectFieldOffset(UNSAFE, "next", Node.class);
 516 
 517     }
 518 
 519     /* ---------------- Indexing -------------- */
 520 
 521     /**
 522      * Index nodes represent the levels of the skip list.  Note that
 523      * even though both Nodes and Indexes have forward-pointing
 524      * fields, they have different types and are handled in different
 525      * ways, that can't nicely be captured by placing field in a
 526      * shared abstract class.
 527      */
 528     static class Index<K,V> {
 529         final Node<K,V> node;
 530         final Index<K,V> down;
 531         volatile Index<K,V> right;
 532 
 533         /**
 534          * Creates index node with given values.
 535          */
 536         Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
 537             this.node = node;
 538             this.down = down;
 539             this.right = right;
 540         }
 541 





 542         /**
 543          * compareAndSet right field
 544          */
 545         final boolean casRight(Index<K,V> cmp, Index<K,V> val) {
 546             return UNSAFE.compareAndSwapObject(this, rightOffset, cmp, val);
 547         }
 548 
 549         /**
 550          * Returns true if the node this indexes has been deleted.
 551          * @return true if indexed node is known to be deleted
 552          */
 553         final boolean indexesDeletedNode() {
 554             return node.value == null;
 555         }
 556 
 557         /**
 558          * Tries to CAS newSucc as successor.  To minimize races with
 559          * unlink that may lose this index node, if the node being
 560          * indexed is known to be deleted, it doesn't try to link in.
 561          * @param succ the expected current successor
 562          * @param newSucc the new successor
 563          * @return true if successful
 564          */
 565         final boolean link(Index<K,V> succ, Index<K,V> newSucc) {
 566             Node<K,V> n = node;
 567             newSucc.right = succ;
 568             return n.value != null && casRight(succ, newSucc);
 569         }
 570 
 571         /**
 572          * Tries to CAS right field to skip over apparent successor
 573          * succ.  Fails (forcing a retraversal by caller) if this node
 574          * is known to be deleted.
 575          * @param succ the expected current successor
 576          * @return true if successful
 577          */
 578         final boolean unlink(Index<K,V> succ) {
 579             return !indexesDeletedNode() && casRight(succ, succ.right);
 580         }
 581 
 582         // Unsafe mechanics
 583         private static final sun.misc.Unsafe UNSAFE = sun.misc.Unsafe.getUnsafe();
 584         private static final long rightOffset =
 585             objectFieldOffset(UNSAFE, "right", Index.class);
 586 
 587     }
 588 
 589     /* ---------------- Head nodes -------------- */
 590 
 591     /**
 592      * Nodes heading each level keep track of their level.
 593      */
 594     static final class HeadIndex<K,V> extends Index<K,V> {
 595         final int level;
 596         HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {
 597             super(node, down, right);
 598             this.level = level;
 599         }
 600     }
 601 
 602     /* ---------------- Comparison utilities -------------- */
 603 
 604     /**
 605      * Represents a key with a comparator as a Comparable.
 606      *


 616      * Comparators vs Comparables, which seems like the right
 617      * tradeoff.
 618      */
 619     static final class ComparableUsingComparator<K> implements Comparable<K> {
 620         final K actualKey;
 621         final Comparator<? super K> cmp;
 622         ComparableUsingComparator(K key, Comparator<? super K> cmp) {
 623             this.actualKey = key;
 624             this.cmp = cmp;
 625         }
 626         public int compareTo(K k2) {
 627             return cmp.compare(actualKey, k2);
 628         }
 629     }
 630 
 631     /**
 632      * If using comparator, return a ComparableUsingComparator, else
 633      * cast key as Comparable, which may cause ClassCastException,
 634      * which is propagated back to caller.
 635      */
 636     private Comparable<? super K> comparable(Object key)
 637             throws ClassCastException {
 638         if (key == null)
 639             throw new NullPointerException();
 640         if (comparator != null)
 641             return new ComparableUsingComparator<K>((K)key, comparator);
 642         else
 643             return (Comparable<? super K>)key;
 644     }
 645 
 646     /**
 647      * Compares using comparator or natural ordering. Used when the
 648      * ComparableUsingComparator approach doesn't apply.
 649      */
 650     int compare(K k1, K k2) throws ClassCastException {
 651         Comparator<? super K> cmp = comparator;
 652         if (cmp != null)
 653             return cmp.compare(k1, k2);
 654         else
 655             return ((Comparable<? super K>)k1).compareTo(k2);
 656     }
 657 


 805      * @return the value, or null if absent
 806      */
 807     private V doGet(Object okey) {
 808         Comparable<? super K> key = comparable(okey);
 809         Node<K,V> bound = null;
 810         Index<K,V> q = head;
 811         Index<K,V> r = q.right;
 812         Node<K,V> n;
 813         K k;
 814         int c;
 815         for (;;) {
 816             Index<K,V> d;
 817             // Traverse rights
 818             if (r != null && (n = r.node) != bound && (k = n.key) != null) {
 819                 if ((c = key.compareTo(k)) > 0) {
 820                     q = r;
 821                     r = r.right;
 822                     continue;
 823                 } else if (c == 0) {
 824                     Object v = n.value;
 825                     return (v != null) ? (V)v : getUsingFindNode(key);
 826                 } else
 827                     bound = n;
 828             }
 829 
 830             // Traverse down
 831             if ((d = q.down) != null) {
 832                 q = d;
 833                 r = d.right;
 834             } else
 835                 break;
 836         }
 837 
 838         // Traverse nexts
 839         for (n = q.node.next;  n != null; n = n.next) {
 840             if ((k = n.key) != null) {
 841                 if ((c = key.compareTo(k)) == 0) {
 842                     Object v = n.value;
 843                     return (v != null) ? (V)v : getUsingFindNode(key);
 844                 } else if (c < 0)
 845                     break;
 846             }
 847         }
 848         return null;
 849     }
 850 
 851     /**
 852      * Performs map.get via findNode.  Used as a backup if doGet
 853      * encounters an in-progress deletion.
 854      * @param key the key
 855      * @return the value, or null if absent
 856      */
 857     private V getUsingFindNode(Comparable<? super K> key) {
 858         /*
 859          * Loop needed here and elsewhere in case value field goes
 860          * null just as it is about to be returned, in which case we
 861          * lost a race with a deletion, so must retry.
 862          */
 863         for (;;) {


 920                     insertIndex(z, level);
 921                 return null;
 922             }
 923         }
 924     }
 925 
 926     /**
 927      * Returns a random level for inserting a new node.
 928      * Hardwired to k=1, p=0.5, max 31 (see above and
 929      * Pugh's "Skip List Cookbook", sec 3.4).
 930      *
 931      * This uses the simplest of the generators described in George
 932      * Marsaglia's "Xorshift RNGs" paper.  This is not a high-quality
 933      * generator but is acceptable here.
 934      */
 935     private int randomLevel() {
 936         int x = randomSeed;
 937         x ^= x << 13;
 938         x ^= x >>> 17;
 939         randomSeed = x ^= x << 5;
 940         if ((x & 0x80000001) != 0) // test highest and lowest bits
 941             return 0;
 942         int level = 1;
 943         while (((x >>>= 1) & 1) != 0) ++level;
 944         return level;
 945     }
 946 
 947     /**
 948      * Creates and adds index nodes for the given node.
 949      * @param z the node
 950      * @param level the level of the index
 951      */
 952     private void insertIndex(Node<K,V> z, int level) {
 953         HeadIndex<K,V> h = head;
 954         int max = h.level;
 955 
 956         if (level <= max) {
 957             Index<K,V> idx = null;
 958             for (int i = 1; i <= level; ++i)
 959                 idx = new Index<K,V>(z, idx, null);
 960             addIndex(idx, h, level);


1233          * because this doesn't use comparisons.  So traversals of
1234          * both levels are folded together.
1235          */
1236         Index<K,V> q = head;
1237         for (;;) {
1238             Index<K,V> d, r;
1239             if ((r = q.right) != null) {
1240                 if (r.indexesDeletedNode()) {
1241                     q.unlink(r);
1242                     q = head; // restart
1243                 }
1244                 else
1245                     q = r;
1246             } else if ((d = q.down) != null) {
1247                 q = d;
1248             } else {
1249                 Node<K,V> b = q.node;
1250                 Node<K,V> n = b.next;
1251                 for (;;) {
1252                     if (n == null)
1253                         return b.isBaseHeader() ? null : b;
1254                     Node<K,V> f = n.next;            // inconsistent read
1255                     if (n != b.next)
1256                         break;
1257                     Object v = n.value;
1258                     if (v == null) {                 // n is deleted
1259                         n.helpDelete(b, f);
1260                         break;
1261                     }
1262                     if (v == n || b.value == null)   // b is deleted
1263                         break;
1264                     b = n;
1265                     n = f;
1266                 }
1267                 q = head; // restart
1268             }
1269         }
1270     }
1271 
1272     /**
1273      * Specialized variant of findPredecessor to get predecessor of last


1351 
1352     // Control values OR'ed as arguments to findNear
1353 
1354     private static final int EQ = 1;
1355     private static final int LT = 2;
1356     private static final int GT = 0; // Actually checked as !LT
1357 
1358     /**
1359      * Utility for ceiling, floor, lower, higher methods.
1360      * @param kkey the key
1361      * @param rel the relation -- OR'ed combination of EQ, LT, GT
1362      * @return nearest node fitting relation, or null if no such
1363      */
1364     Node<K,V> findNear(K kkey, int rel) {
1365         Comparable<? super K> key = comparable(kkey);
1366         for (;;) {
1367             Node<K,V> b = findPredecessor(key);
1368             Node<K,V> n = b.next;
1369             for (;;) {
1370                 if (n == null)
1371                     return ((rel & LT) == 0 || b.isBaseHeader()) ? null : b;
1372                 Node<K,V> f = n.next;
1373                 if (n != b.next)                  // inconsistent read
1374                     break;
1375                 Object v = n.value;
1376                 if (v == null) {                  // n is deleted
1377                     n.helpDelete(b, f);
1378                     break;
1379                 }
1380                 if (v == n || b.value == null)    // b is deleted
1381                     break;
1382                 int c = key.compareTo(n.key);
1383                 if ((c == 0 && (rel & EQ) != 0) ||
1384                     (c <  0 && (rel & LT) == 0))
1385                     return n;
1386                 if ( c <= 0 && (rel & LT) != 0)
1387                     return b.isBaseHeader() ? null : b;
1388                 b = n;
1389                 n = f;
1390             }
1391         }
1392     }
1393 
1394     /**
1395      * Returns SimpleImmutableEntry for results of findNear.
1396      * @param key the key
1397      * @param rel the relation -- OR'ed combination of EQ, LT, GT
1398      * @return Entry fitting relation, or null if no such
1399      */
1400     AbstractMap.SimpleImmutableEntry<K,V> getNear(K key, int rel) {
1401         for (;;) {
1402             Node<K,V> n = findNear(key, rel);
1403             if (n == null)
1404                 return null;
1405             AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
1406             if (e != null)
1407                 return e;


1721      * contains more than <tt>Integer.MAX_VALUE</tt> elements, it
1722      * returns <tt>Integer.MAX_VALUE</tt>.
1723      *
1724      * <p>Beware that, unlike in most collections, this method is
1725      * <em>NOT</em> a constant-time operation. Because of the
1726      * asynchronous nature of these maps, determining the current
1727      * number of elements requires traversing them all to count them.
1728      * Additionally, it is possible for the size to change during
1729      * execution of this method, in which case the returned result
1730      * will be inaccurate. Thus, this method is typically not very
1731      * useful in concurrent applications.
1732      *
1733      * @return the number of elements in this map
1734      */
1735     public int size() {
1736         long count = 0;
1737         for (Node<K,V> n = findFirst(); n != null; n = n.next) {
1738             if (n.getValidValue() != null)
1739                 ++count;
1740         }
1741         return (count >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int) count;
1742     }
1743 
1744     /**
1745      * Returns <tt>true</tt> if this map contains no key-value mappings.
1746      * @return <tt>true</tt> if this map contains no key-value mappings
1747      */
1748     public boolean isEmpty() {
1749         return findFirst() == null;
1750     }
1751 
1752     /**
1753      * Removes all of the mappings from this map.
1754      */
1755     public void clear() {
1756         initialize();
1757     }
1758 
1759     /* ---------------- View methods -------------- */
1760 
1761     /*


2076 
2077     /**
2078      * Returns a key-value mapping associated with the greatest key
2079      * strictly less than the given key, or <tt>null</tt> if there is
2080      * no such key. The returned entry does <em>not</em> support the
2081      * <tt>Entry.setValue</tt> method.
2082      *
2083      * @throws ClassCastException {@inheritDoc}
2084      * @throws NullPointerException if the specified key is null
2085      */
2086     public Map.Entry<K,V> lowerEntry(K key) {
2087         return getNear(key, LT);
2088     }
2089 
2090     /**
2091      * @throws ClassCastException {@inheritDoc}
2092      * @throws NullPointerException if the specified key is null
2093      */
2094     public K lowerKey(K key) {
2095         Node<K,V> n = findNear(key, LT);
2096         return (n == null) ? null : n.key;
2097     }
2098 
2099     /**
2100      * Returns a key-value mapping associated with the greatest key
2101      * less than or equal to the given key, or <tt>null</tt> if there
2102      * is no such key. The returned entry does <em>not</em> support
2103      * the <tt>Entry.setValue</tt> method.
2104      *
2105      * @param key the key
2106      * @throws ClassCastException {@inheritDoc}
2107      * @throws NullPointerException if the specified key is null
2108      */
2109     public Map.Entry<K,V> floorEntry(K key) {
2110         return getNear(key, LT|EQ);
2111     }
2112 
2113     /**
2114      * @param key the key
2115      * @throws ClassCastException {@inheritDoc}
2116      * @throws NullPointerException if the specified key is null
2117      */
2118     public K floorKey(K key) {
2119         Node<K,V> n = findNear(key, LT|EQ);
2120         return (n == null) ? null : n.key;
2121     }
2122 
2123     /**
2124      * Returns a key-value mapping associated with the least key
2125      * greater than or equal to the given key, or <tt>null</tt> if
2126      * there is no such entry. The returned entry does <em>not</em>
2127      * support the <tt>Entry.setValue</tt> method.
2128      *
2129      * @throws ClassCastException {@inheritDoc}
2130      * @throws NullPointerException if the specified key is null
2131      */
2132     public Map.Entry<K,V> ceilingEntry(K key) {
2133         return getNear(key, GT|EQ);
2134     }
2135 
2136     /**
2137      * @throws ClassCastException {@inheritDoc}
2138      * @throws NullPointerException if the specified key is null
2139      */
2140     public K ceilingKey(K key) {
2141         Node<K,V> n = findNear(key, GT|EQ);
2142         return (n == null) ? null : n.key;
2143     }
2144 
2145     /**
2146      * Returns a key-value mapping associated with the least key
2147      * strictly greater than the given key, or <tt>null</tt> if there
2148      * is no such key. The returned entry does <em>not</em> support
2149      * the <tt>Entry.setValue</tt> method.
2150      *
2151      * @param key the key
2152      * @throws ClassCastException {@inheritDoc}
2153      * @throws NullPointerException if the specified key is null
2154      */
2155     public Map.Entry<K,V> higherEntry(K key) {
2156         return getNear(key, GT);
2157     }
2158 
2159     /**
2160      * @param key the key
2161      * @throws ClassCastException {@inheritDoc}
2162      * @throws NullPointerException if the specified key is null
2163      */
2164     public K higherKey(K key) {
2165         Node<K,V> n = findNear(key, GT);
2166         return (n == null) ? null : n.key;
2167     }
2168 
2169     /**
2170      * Returns a key-value mapping associated with the least
2171      * 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> firstEntry() {
2176         for (;;) {
2177             Node<K,V> n = findFirst();
2178             if (n == null)
2179                 return null;
2180             AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
2181             if (e != null)
2182                 return e;
2183         }
2184     }
2185 
2186     /**


2319     Iterator<Map.Entry<K,V>> entryIterator() {
2320         return new EntryIterator();
2321     }
2322 
2323     /* ---------------- View Classes -------------- */
2324 
2325     /*
2326      * View classes are static, delegating to a ConcurrentNavigableMap
2327      * to allow use by SubMaps, which outweighs the ugliness of
2328      * needing type-tests for Iterator methods.
2329      */
2330 
2331     static final <E> List<E> toList(Collection<E> c) {
2332         // Using size() here would be a pessimization.
2333         List<E> list = new ArrayList<E>();
2334         for (E e : c)
2335             list.add(e);
2336         return list;
2337     }
2338 
2339     static final class KeySet<E>
2340             extends AbstractSet<E> implements NavigableSet<E> {
2341         private final ConcurrentNavigableMap<E,Object> m;
2342         KeySet(ConcurrentNavigableMap<E,Object> map) { m = map; }
2343         public int size() { return m.size(); }
2344         public boolean isEmpty() { return m.isEmpty(); }
2345         public boolean contains(Object o) { return m.containsKey(o); }
2346         public boolean remove(Object o) { return m.remove(o) != null; }
2347         public void clear() { m.clear(); }
2348         public E lower(E e) { return m.lowerKey(e); }
2349         public E floor(E e) { return m.floorKey(e); }
2350         public E ceiling(E e) { return m.ceilingKey(e); }
2351         public E higher(E e) { return m.higherKey(e); }
2352         public Comparator<? super E> comparator() { return m.comparator(); }
2353         public E first() { return m.firstKey(); }
2354         public E last() { return m.lastKey(); }
2355         public E pollFirst() {
2356             Map.Entry<E,Object> e = m.pollFirstEntry();
2357             return (e == null) ? null : e.getKey();
2358         }
2359         public E pollLast() {
2360             Map.Entry<E,Object> e = m.pollLastEntry();
2361             return (e == null) ? null : e.getKey();
2362         }
2363         public Iterator<E> iterator() {
2364             if (m instanceof ConcurrentSkipListMap)
2365                 return ((ConcurrentSkipListMap<E,Object>)m).keyIterator();
2366             else
2367                 return ((ConcurrentSkipListMap.SubMap<E,Object>)m).keyIterator();
2368         }
2369         public boolean equals(Object o) {
2370             if (o == this)
2371                 return true;
2372             if (!(o instanceof Set))
2373                 return false;
2374             Collection<?> c = (Collection<?>) o;
2375             try {
2376                 return containsAll(c) && c.containsAll(this);
2377             } catch (ClassCastException unused)   {
2378                 return false;
2379             } catch (NullPointerException unused) {
2380                 return false;
2381             }


2688                 K k = n.key;
2689                 if (!inBounds(k))
2690                     return null;
2691                 V v = m.doRemove(k, null);
2692                 if (v != null)
2693                     return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2694             }
2695         }
2696 
2697         /**
2698          * Submap version of ConcurrentSkipListMap.getNearEntry
2699          */
2700         private Map.Entry<K,V> getNearEntry(K key, int rel) {
2701             if (isDescending) { // adjust relation for direction
2702                 if ((rel & m.LT) == 0)
2703                     rel |= m.LT;
2704                 else
2705                     rel &= ~m.LT;
2706             }
2707             if (tooLow(key))
2708                 return ((rel & m.LT) != 0) ? null : lowestEntry();
2709             if (tooHigh(key))
2710                 return ((rel & m.LT) != 0) ? highestEntry() : null;
2711             for (;;) {
2712                 Node<K,V> n = m.findNear(key, rel);
2713                 if (n == null || !inBounds(n.key))
2714                     return null;
2715                 K k = n.key;
2716                 V v = n.getValidValue();
2717                 if (v != null)
2718                     return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2719             }
2720         }
2721 
2722         // Almost the same as getNearEntry, except for keys
2723         private K getNearKey(K key, int rel) {
2724             if (isDescending) { // adjust relation for direction
2725                 if ((rel & m.LT) == 0)
2726                     rel |= m.LT;
2727                 else
2728                     rel &= ~m.LT;
2729             }
2730             if (tooLow(key)) {


2761 
2762         public boolean containsKey(Object key) {
2763             if (key == null) throw new NullPointerException();
2764             K k = (K)key;
2765             return inBounds(k) && m.containsKey(k);
2766         }
2767 
2768         public V get(Object key) {
2769             if (key == null) throw new NullPointerException();
2770             K k = (K)key;
2771             return ((!inBounds(k)) ? null : m.get(k));
2772         }
2773 
2774         public V put(K key, V value) {
2775             checkKeyBounds(key);
2776             return m.put(key, value);
2777         }
2778 
2779         public V remove(Object key) {
2780             K k = (K)key;
2781             return (!inBounds(k)) ? null : m.remove(k);
2782         }
2783 
2784         public int size() {
2785             long count = 0;
2786             for (ConcurrentSkipListMap.Node<K,V> n = loNode();
2787                  isBeforeEnd(n);
2788                  n = n.next) {
2789                 if (n.getValidValue() != null)
2790                     ++count;
2791             }
2792             return count >= Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)count;
2793         }
2794 
2795         public boolean isEmpty() {
2796             return !isBeforeEnd(loNode());
2797         }
2798 
2799         public boolean containsValue(Object value) {
2800             if (value == null)
2801                 throw new NullPointerException();
2802             for (ConcurrentSkipListMap.Node<K,V> n = loNode();
2803                  isBeforeEnd(n);
2804                  n = n.next) {
2805                 V v = n.getValidValue();
2806                 if (v != null && value.equals(v))
2807                     return true;
2808             }
2809             return false;
2810         }
2811 
2812         public void clear() {


2950             return getNearKey(key, (m.LT));
2951         }
2952 
2953         public Map.Entry<K,V> floorEntry(K key) {
2954             return getNearEntry(key, (m.LT|m.EQ));
2955         }
2956 
2957         public K floorKey(K key) {
2958             return getNearKey(key, (m.LT|m.EQ));
2959         }
2960 
2961         public Map.Entry<K,V> higherEntry(K key) {
2962             return getNearEntry(key, (m.GT));
2963         }
2964 
2965         public K higherKey(K key) {
2966             return getNearKey(key, (m.GT));
2967         }
2968 
2969         public K firstKey() {
2970             return isDescending ? highestKey() : lowestKey();
2971         }
2972 
2973         public K lastKey() {
2974             return isDescending ? lowestKey() : highestKey();
2975         }
2976 
2977         public Map.Entry<K,V> firstEntry() {
2978             return isDescending ? highestEntry() : lowestEntry();
2979         }
2980 
2981         public Map.Entry<K,V> lastEntry() {
2982             return isDescending ? lowestEntry() : highestEntry();
2983         }
2984 
2985         public Map.Entry<K,V> pollFirstEntry() {
2986             return isDescending ? removeHighest() : removeLowest();
2987         }
2988 
2989         public Map.Entry<K,V> pollLastEntry() {
2990             return isDescending ? removeLowest() : removeHighest();
2991         }
2992 
2993         /* ---------------- Submap Views -------------- */
2994 
2995         public NavigableSet<K> keySet() {
2996             KeySet<K> ks = keySetView;
2997             return (ks != null) ? ks : (keySetView = new KeySet(this));
2998         }
2999 
3000         public NavigableSet<K> navigableKeySet() {
3001             KeySet<K> ks = keySetView;
3002             return (ks != null) ? ks : (keySetView = new KeySet(this));
3003         }
3004 
3005         public Collection<V> values() {
3006             Collection<V> vs = valuesView;
3007             return (vs != null) ? vs : (valuesView = new Values(this));
3008         }
3009 
3010         public Set<Map.Entry<K,V>> entrySet() {


3119             }
3120         }
3121 
3122         final class SubMapKeyIterator extends SubMapIter<K> {
3123             public K next() {
3124                 Node<K,V> n = next;
3125                 advance();
3126                 return n.key;
3127             }
3128         }
3129 
3130         final class SubMapEntryIterator extends SubMapIter<Map.Entry<K,V>> {
3131             public Map.Entry<K,V> next() {
3132                 Node<K,V> n = next;
3133                 V v = nextValue;
3134                 advance();
3135                 return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
3136             }
3137         }
3138     }
3139 
3140     // Unsafe mechanics
3141     private static final sun.misc.Unsafe UNSAFE = sun.misc.Unsafe.getUnsafe();
3142     private static final long headOffset =
3143         objectFieldOffset(UNSAFE, "head", ConcurrentSkipListMap.class);
3144 
3145     static long objectFieldOffset(sun.misc.Unsafe UNSAFE,
3146                                   String field, Class<?> klazz) {
3147         try {
3148             return UNSAFE.objectFieldOffset(klazz.getDeclaredField(field));
3149         } catch (NoSuchFieldException e) {
3150             // Convert Exception to corresponding Error
3151             NoSuchFieldError error = new NoSuchFieldError(field);
3152             error.initCause(e);
3153             throw error;
3154         }
3155     }
3156 
3157 }