Print this page


Split Close
Expand all
Collapse all
          --- old/src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java
          +++ new/src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java
↓ open down ↓ 366 lines elided ↑ open up ↑
 367  367      final void initialize() {
 368  368          keySet = null;
 369  369          entrySet = null;
 370  370          values = null;
 371  371          descendingMap = null;
 372  372          randomSeed = seedGenerator.nextInt() | 0x0100; // ensure nonzero
 373  373          head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),
 374  374                                    null, null, 1);
 375  375      }
 376  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  377      /**
 384  378       * compareAndSet head node
 385  379       */
 386  380      private boolean casHead(HeadIndex<K,V> cmp, HeadIndex<K,V> val) {
 387      -        return headUpdater.compareAndSet(this, cmp, val);
      381 +        return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val);
 388  382      }
 389  383  
 390  384      /* ---------------- Nodes -------------- */
 391  385  
 392  386      /**
 393  387       * Nodes hold keys and values, and are singly linked in sorted
 394  388       * order, possibly with some intervening marker nodes. The list is
 395  389       * headed by a dummy node accessible as head.node. The value field
 396  390       * is declared only as Object because it takes special non-V
 397  391       * values for marker and header nodes.
↓ open down ↓ 18 lines elided ↑ open up ↑
 416  410           * have null keys, a fact that is exploited in a few places,
 417  411           * but this doesn't distinguish markers from the base-level
 418  412           * header node (head.node), which also has a null key.
 419  413           */
 420  414          Node(Node<K,V> next) {
 421  415              this.key = null;
 422  416              this.value = this;
 423  417              this.next = next;
 424  418          }
 425  419  
 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  420          /**
 437  421           * compareAndSet value field
 438  422           */
 439  423          boolean casValue(Object cmp, Object val) {
 440      -            return valueUpdater.compareAndSet(this, cmp, val);
      424 +            return UNSAFE.compareAndSwapObject(this, valueOffset, cmp, val);
 441  425          }
 442  426  
 443  427          /**
 444  428           * compareAndSet next field
 445  429           */
 446  430          boolean casNext(Node<K,V> cmp, Node<K,V> val) {
 447      -            return nextUpdater.compareAndSet(this, cmp, val);
      431 +            return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
 448  432          }
 449  433  
 450  434          /**
 451  435           * Returns true if this node is a marker. This method isn't
 452  436           * actually called in any current code checking for markers
 453  437           * because callers will have already read value field and need
 454  438           * to use that read (not another done here) and so directly
 455  439           * test if value points to node.
 456  440           * @param n a possibly null reference to a node
 457  441           * @return true if this node is a marker node
↓ open down ↓ 57 lines elided ↑ open up ↑
 515  499           * Creates and returns a new SimpleImmutableEntry holding current
 516  500           * mapping if this node holds a valid value, else null.
 517  501           * @return new entry or null
 518  502           */
 519  503          AbstractMap.SimpleImmutableEntry<K,V> createSnapshot() {
 520  504              V v = getValidValue();
 521  505              if (v == null)
 522  506                  return null;
 523  507              return new AbstractMap.SimpleImmutableEntry<K,V>(key, v);
 524  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 +
 525  517      }
 526  518  
 527  519      /* ---------------- Indexing -------------- */
 528  520  
 529  521      /**
 530  522       * Index nodes represent the levels of the skip list.  Note that
 531  523       * even though both Nodes and Indexes have forward-pointing
 532  524       * fields, they have different types and are handled in different
 533  525       * ways, that can't nicely be captured by placing field in a
 534  526       * shared abstract class.
↓ open down ↓ 5 lines elided ↑ open up ↑
 540  532  
 541  533          /**
 542  534           * Creates index node with given values.
 543  535           */
 544  536          Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
 545  537              this.node = node;
 546  538              this.down = down;
 547  539              this.right = right;
 548  540          }
 549  541  
 550      -        /** Updater for casRight */
 551      -        static final AtomicReferenceFieldUpdater<Index, Index>
 552      -            rightUpdater = AtomicReferenceFieldUpdater.newUpdater
 553      -            (Index.class, Index.class, "right");
 554      -
 555  542          /**
 556  543           * compareAndSet right field
 557  544           */
 558  545          final boolean casRight(Index<K,V> cmp, Index<K,V> val) {
 559      -            return rightUpdater.compareAndSet(this, cmp, val);
      546 +            return UNSAFE.compareAndSwapObject(this, rightOffset, cmp, val);
 560  547          }
 561  548  
 562  549          /**
 563  550           * Returns true if the node this indexes has been deleted.
 564  551           * @return true if indexed node is known to be deleted
 565  552           */
 566  553          final boolean indexesDeletedNode() {
 567  554              return node.value == null;
 568  555          }
 569  556  
↓ open down ↓ 14 lines elided ↑ open up ↑
 584  571          /**
 585  572           * Tries to CAS right field to skip over apparent successor
 586  573           * succ.  Fails (forcing a retraversal by caller) if this node
 587  574           * is known to be deleted.
 588  575           * @param succ the expected current successor
 589  576           * @return true if successful
 590  577           */
 591  578          final boolean unlink(Index<K,V> succ) {
 592  579              return !indexesDeletedNode() && casRight(succ, succ.right);
 593  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 +
 594  587      }
 595  588  
 596  589      /* ---------------- Head nodes -------------- */
 597  590  
 598  591      /**
 599  592       * Nodes heading each level keep track of their level.
 600  593       */
 601  594      static final class HeadIndex<K,V> extends Index<K,V> {
 602  595          final int level;
 603  596          HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {
↓ open down ↓ 29 lines elided ↑ open up ↑
 633  626          public int compareTo(K k2) {
 634  627              return cmp.compare(actualKey, k2);
 635  628          }
 636  629      }
 637  630  
 638  631      /**
 639  632       * If using comparator, return a ComparableUsingComparator, else
 640  633       * cast key as Comparable, which may cause ClassCastException,
 641  634       * which is propagated back to caller.
 642  635       */
 643      -    private Comparable<? super K> comparable(Object key) throws ClassCastException {
      636 +    private Comparable<? super K> comparable(Object key)
      637 +            throws ClassCastException {
 644  638          if (key == null)
 645  639              throw new NullPointerException();
 646  640          if (comparator != null)
 647  641              return new ComparableUsingComparator<K>((K)key, comparator);
 648  642          else
 649  643              return (Comparable<? super K>)key;
 650  644      }
 651  645  
 652  646      /**
 653  647       * Compares using comparator or natural ordering. Used when the
↓ open down ↓ 167 lines elided ↑ open up ↑
 821  815          for (;;) {
 822  816              Index<K,V> d;
 823  817              // Traverse rights
 824  818              if (r != null && (n = r.node) != bound && (k = n.key) != null) {
 825  819                  if ((c = key.compareTo(k)) > 0) {
 826  820                      q = r;
 827  821                      r = r.right;
 828  822                      continue;
 829  823                  } else if (c == 0) {
 830  824                      Object v = n.value;
 831      -                    return (v != null)? (V)v : getUsingFindNode(key);
      825 +                    return (v != null) ? (V)v : getUsingFindNode(key);
 832  826                  } else
 833  827                      bound = n;
 834  828              }
 835  829  
 836  830              // Traverse down
 837  831              if ((d = q.down) != null) {
 838  832                  q = d;
 839  833                  r = d.right;
 840  834              } else
 841  835                  break;
 842  836          }
 843  837  
 844  838          // Traverse nexts
 845  839          for (n = q.node.next;  n != null; n = n.next) {
 846  840              if ((k = n.key) != null) {
 847  841                  if ((c = key.compareTo(k)) == 0) {
 848  842                      Object v = n.value;
 849      -                    return (v != null)? (V)v : getUsingFindNode(key);
      843 +                    return (v != null) ? (V)v : getUsingFindNode(key);
 850  844                  } else if (c < 0)
 851  845                      break;
 852  846              }
 853  847          }
 854  848          return null;
 855  849      }
 856  850  
 857  851      /**
 858  852       * Performs map.get via findNode.  Used as a backup if doGet
 859  853       * encounters an in-progress deletion.
↓ open down ↓ 76 lines elided ↑ open up ↑
 936  930       *
 937  931       * This uses the simplest of the generators described in George
 938  932       * Marsaglia's "Xorshift RNGs" paper.  This is not a high-quality
 939  933       * generator but is acceptable here.
 940  934       */
 941  935      private int randomLevel() {
 942  936          int x = randomSeed;
 943  937          x ^= x << 13;
 944  938          x ^= x >>> 17;
 945  939          randomSeed = x ^= x << 5;
 946      -        if ((x & 0x8001) != 0) // test highest and lowest bits
      940 +        if ((x & 0x80000001) != 0) // test highest and lowest bits
 947  941              return 0;
 948  942          int level = 1;
 949  943          while (((x >>>= 1) & 1) != 0) ++level;
 950  944          return level;
 951  945      }
 952  946  
 953  947      /**
 954  948       * Creates and adds index nodes for the given node.
 955  949       * @param z the node
 956  950       * @param level the level of the index
↓ open down ↓ 292 lines elided ↑ open up ↑
1249 1243                  }
1250 1244                  else
1251 1245                      q = r;
1252 1246              } else if ((d = q.down) != null) {
1253 1247                  q = d;
1254 1248              } else {
1255 1249                  Node<K,V> b = q.node;
1256 1250                  Node<K,V> n = b.next;
1257 1251                  for (;;) {
1258 1252                      if (n == null)
1259      -                        return (b.isBaseHeader())? null : b;
     1253 +                        return b.isBaseHeader() ? null : b;
1260 1254                      Node<K,V> f = n.next;            // inconsistent read
1261 1255                      if (n != b.next)
1262 1256                          break;
1263 1257                      Object v = n.value;
1264 1258                      if (v == null) {                 // n is deleted
1265 1259                          n.helpDelete(b, f);
1266 1260                          break;
1267 1261                      }
1268 1262                      if (v == n || b.value == null)   // b is deleted
1269 1263                          break;
↓ open down ↓ 97 lines elided ↑ open up ↑
1367 1361       * @param rel the relation -- OR'ed combination of EQ, LT, GT
1368 1362       * @return nearest node fitting relation, or null if no such
1369 1363       */
1370 1364      Node<K,V> findNear(K kkey, int rel) {
1371 1365          Comparable<? super K> key = comparable(kkey);
1372 1366          for (;;) {
1373 1367              Node<K,V> b = findPredecessor(key);
1374 1368              Node<K,V> n = b.next;
1375 1369              for (;;) {
1376 1370                  if (n == null)
1377      -                    return ((rel & LT) == 0 || b.isBaseHeader())? null : b;
     1371 +                    return ((rel & LT) == 0 || b.isBaseHeader()) ? null : b;
1378 1372                  Node<K,V> f = n.next;
1379 1373                  if (n != b.next)                  // inconsistent read
1380 1374                      break;
1381 1375                  Object v = n.value;
1382 1376                  if (v == null) {                  // n is deleted
1383 1377                      n.helpDelete(b, f);
1384 1378                      break;
1385 1379                  }
1386 1380                  if (v == n || b.value == null)    // b is deleted
1387 1381                      break;
1388 1382                  int c = key.compareTo(n.key);
1389 1383                  if ((c == 0 && (rel & EQ) != 0) ||
1390 1384                      (c <  0 && (rel & LT) == 0))
1391 1385                      return n;
1392 1386                  if ( c <= 0 && (rel & LT) != 0)
1393      -                    return (b.isBaseHeader())? null : b;
     1387 +                    return b.isBaseHeader() ? null : b;
1394 1388                  b = n;
1395 1389                  n = f;
1396 1390              }
1397 1391          }
1398 1392      }
1399 1393  
1400 1394      /**
1401 1395       * Returns SimpleImmutableEntry for results of findNear.
1402 1396       * @param key the key
1403 1397       * @param rel the relation -- OR'ed combination of EQ, LT, GT
↓ open down ↓ 333 lines elided ↑ open up ↑
1737 1731       * useful in concurrent applications.
1738 1732       *
1739 1733       * @return the number of elements in this map
1740 1734       */
1741 1735      public int size() {
1742 1736          long count = 0;
1743 1737          for (Node<K,V> n = findFirst(); n != null; n = n.next) {
1744 1738              if (n.getValidValue() != null)
1745 1739                  ++count;
1746 1740          }
1747      -        return (count >= Integer.MAX_VALUE)? Integer.MAX_VALUE : (int)count;
     1741 +        return (count >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int) count;
1748 1742      }
1749 1743  
1750 1744      /**
1751 1745       * Returns <tt>true</tt> if this map contains no key-value mappings.
1752 1746       * @return <tt>true</tt> if this map contains no key-value mappings
1753 1747       */
1754 1748      public boolean isEmpty() {
1755 1749          return findFirst() == null;
1756 1750      }
1757 1751  
↓ open down ↓ 334 lines elided ↑ open up ↑
2092 2086      public Map.Entry<K,V> lowerEntry(K key) {
2093 2087          return getNear(key, LT);
2094 2088      }
2095 2089  
2096 2090      /**
2097 2091       * @throws ClassCastException {@inheritDoc}
2098 2092       * @throws NullPointerException if the specified key is null
2099 2093       */
2100 2094      public K lowerKey(K key) {
2101 2095          Node<K,V> n = findNear(key, LT);
2102      -        return (n == null)? null : n.key;
     2096 +        return (n == null) ? null : n.key;
2103 2097      }
2104 2098  
2105 2099      /**
2106 2100       * Returns a key-value mapping associated with the greatest key
2107 2101       * less than or equal to the given key, or <tt>null</tt> if there
2108 2102       * is no such key. The returned entry does <em>not</em> support
2109 2103       * the <tt>Entry.setValue</tt> method.
2110 2104       *
2111 2105       * @param key the key
2112 2106       * @throws ClassCastException {@inheritDoc}
↓ open down ↓ 3 lines elided ↑ open up ↑
2116 2110          return getNear(key, LT|EQ);
2117 2111      }
2118 2112  
2119 2113      /**
2120 2114       * @param key the key
2121 2115       * @throws ClassCastException {@inheritDoc}
2122 2116       * @throws NullPointerException if the specified key is null
2123 2117       */
2124 2118      public K floorKey(K key) {
2125 2119          Node<K,V> n = findNear(key, LT|EQ);
2126      -        return (n == null)? null : n.key;
     2120 +        return (n == null) ? null : n.key;
2127 2121      }
2128 2122  
2129 2123      /**
2130 2124       * Returns a key-value mapping associated with the least key
2131 2125       * greater than or equal to the given key, or <tt>null</tt> if
2132 2126       * there is no such entry. The returned entry does <em>not</em>
2133 2127       * support the <tt>Entry.setValue</tt> method.
2134 2128       *
2135 2129       * @throws ClassCastException {@inheritDoc}
2136 2130       * @throws NullPointerException if the specified key is null
↓ open down ↓ 1 lines elided ↑ open up ↑
2138 2132      public Map.Entry<K,V> ceilingEntry(K key) {
2139 2133          return getNear(key, GT|EQ);
2140 2134      }
2141 2135  
2142 2136      /**
2143 2137       * @throws ClassCastException {@inheritDoc}
2144 2138       * @throws NullPointerException if the specified key is null
2145 2139       */
2146 2140      public K ceilingKey(K key) {
2147 2141          Node<K,V> n = findNear(key, GT|EQ);
2148      -        return (n == null)? null : n.key;
     2142 +        return (n == null) ? null : n.key;
2149 2143      }
2150 2144  
2151 2145      /**
2152 2146       * Returns a key-value mapping associated with the least key
2153 2147       * strictly greater than the given key, or <tt>null</tt> if there
2154 2148       * is no such key. The returned entry does <em>not</em> support
2155 2149       * the <tt>Entry.setValue</tt> method.
2156 2150       *
2157 2151       * @param key the key
2158 2152       * @throws ClassCastException {@inheritDoc}
↓ open down ↓ 3 lines elided ↑ open up ↑
2162 2156          return getNear(key, GT);
2163 2157      }
2164 2158  
2165 2159      /**
2166 2160       * @param key the key
2167 2161       * @throws ClassCastException {@inheritDoc}
2168 2162       * @throws NullPointerException if the specified key is null
2169 2163       */
2170 2164      public K higherKey(K key) {
2171 2165          Node<K,V> n = findNear(key, GT);
2172      -        return (n == null)? null : n.key;
     2166 +        return (n == null) ? null : n.key;
2173 2167      }
2174 2168  
2175 2169      /**
2176 2170       * Returns a key-value mapping associated with the least
2177 2171       * key in this map, or <tt>null</tt> if the map is empty.
2178 2172       * The returned entry does <em>not</em> support
2179 2173       * the <tt>Entry.setValue</tt> method.
2180 2174       */
2181 2175      public Map.Entry<K,V> firstEntry() {
2182 2176          for (;;) {
↓ open down ↓ 152 lines elided ↑ open up ↑
2335 2329       */
2336 2330  
2337 2331      static final <E> List<E> toList(Collection<E> c) {
2338 2332          // Using size() here would be a pessimization.
2339 2333          List<E> list = new ArrayList<E>();
2340 2334          for (E e : c)
2341 2335              list.add(e);
2342 2336          return list;
2343 2337      }
2344 2338  
2345      -    static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
     2339 +    static final class KeySet<E>
     2340 +            extends AbstractSet<E> implements NavigableSet<E> {
2346 2341          private final ConcurrentNavigableMap<E,Object> m;
2347 2342          KeySet(ConcurrentNavigableMap<E,Object> map) { m = map; }
2348 2343          public int size() { return m.size(); }
2349 2344          public boolean isEmpty() { return m.isEmpty(); }
2350 2345          public boolean contains(Object o) { return m.containsKey(o); }
2351 2346          public boolean remove(Object o) { return m.remove(o) != null; }
2352 2347          public void clear() { m.clear(); }
2353 2348          public E lower(E e) { return m.lowerKey(e); }
2354 2349          public E floor(E e) { return m.floorKey(e); }
2355 2350          public E ceiling(E e) { return m.ceilingKey(e); }
2356 2351          public E higher(E e) { return m.higherKey(e); }
2357 2352          public Comparator<? super E> comparator() { return m.comparator(); }
2358 2353          public E first() { return m.firstKey(); }
2359 2354          public E last() { return m.lastKey(); }
2360 2355          public E pollFirst() {
2361 2356              Map.Entry<E,Object> e = m.pollFirstEntry();
2362      -            return e == null? null : e.getKey();
     2357 +            return (e == null) ? null : e.getKey();
2363 2358          }
2364 2359          public E pollLast() {
2365 2360              Map.Entry<E,Object> e = m.pollLastEntry();
2366      -            return e == null? null : e.getKey();
     2361 +            return (e == null) ? null : e.getKey();
2367 2362          }
2368 2363          public Iterator<E> iterator() {
2369 2364              if (m instanceof ConcurrentSkipListMap)
2370 2365                  return ((ConcurrentSkipListMap<E,Object>)m).keyIterator();
2371 2366              else
2372 2367                  return ((ConcurrentSkipListMap.SubMap<E,Object>)m).keyIterator();
2373 2368          }
2374 2369          public boolean equals(Object o) {
2375 2370              if (o == this)
2376 2371                  return true;
↓ open down ↓ 326 lines elided ↑ open up ↑
2703 2698           * Submap version of ConcurrentSkipListMap.getNearEntry
2704 2699           */
2705 2700          private Map.Entry<K,V> getNearEntry(K key, int rel) {
2706 2701              if (isDescending) { // adjust relation for direction
2707 2702                  if ((rel & m.LT) == 0)
2708 2703                      rel |= m.LT;
2709 2704                  else
2710 2705                      rel &= ~m.LT;
2711 2706              }
2712 2707              if (tooLow(key))
2713      -                return ((rel & m.LT) != 0)? null : lowestEntry();
     2708 +                return ((rel & m.LT) != 0) ? null : lowestEntry();
2714 2709              if (tooHigh(key))
2715      -                return ((rel & m.LT) != 0)? highestEntry() : null;
     2710 +                return ((rel & m.LT) != 0) ? highestEntry() : null;
2716 2711              for (;;) {
2717 2712                  Node<K,V> n = m.findNear(key, rel);
2718 2713                  if (n == null || !inBounds(n.key))
2719 2714                      return null;
2720 2715                  K k = n.key;
2721 2716                  V v = n.getValidValue();
2722 2717                  if (v != null)
2723 2718                      return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2724 2719              }
2725 2720          }
↓ open down ↓ 50 lines elided ↑ open up ↑
2776 2771              return ((!inBounds(k)) ? null : m.get(k));
2777 2772          }
2778 2773  
2779 2774          public V put(K key, V value) {
2780 2775              checkKeyBounds(key);
2781 2776              return m.put(key, value);
2782 2777          }
2783 2778  
2784 2779          public V remove(Object key) {
2785 2780              K k = (K)key;
2786      -            return (!inBounds(k))? null : m.remove(k);
     2781 +            return (!inBounds(k)) ? null : m.remove(k);
2787 2782          }
2788 2783  
2789 2784          public int size() {
2790 2785              long count = 0;
2791 2786              for (ConcurrentSkipListMap.Node<K,V> n = loNode();
2792 2787                   isBeforeEnd(n);
2793 2788                   n = n.next) {
2794 2789                  if (n.getValidValue() != null)
2795 2790                      ++count;
2796 2791              }
2797      -            return count >= Integer.MAX_VALUE? Integer.MAX_VALUE : (int)count;
     2792 +            return count >= Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)count;
2798 2793          }
2799 2794  
2800 2795          public boolean isEmpty() {
2801 2796              return !isBeforeEnd(loNode());
2802 2797          }
2803 2798  
2804 2799          public boolean containsValue(Object value) {
2805 2800              if (value == null)
2806 2801                  throw new NullPointerException();
2807 2802              for (ConcurrentSkipListMap.Node<K,V> n = loNode();
↓ open down ↓ 157 lines elided ↑ open up ↑
2965 2960  
2966 2961          public Map.Entry<K,V> higherEntry(K key) {
2967 2962              return getNearEntry(key, (m.GT));
2968 2963          }
2969 2964  
2970 2965          public K higherKey(K key) {
2971 2966              return getNearKey(key, (m.GT));
2972 2967          }
2973 2968  
2974 2969          public K firstKey() {
2975      -            return isDescending? highestKey() : lowestKey();
     2970 +            return isDescending ? highestKey() : lowestKey();
2976 2971          }
2977 2972  
2978 2973          public K lastKey() {
2979      -            return isDescending? lowestKey() : highestKey();
     2974 +            return isDescending ? lowestKey() : highestKey();
2980 2975          }
2981 2976  
2982 2977          public Map.Entry<K,V> firstEntry() {
2983      -            return isDescending? highestEntry() : lowestEntry();
     2978 +            return isDescending ? highestEntry() : lowestEntry();
2984 2979          }
2985 2980  
2986 2981          public Map.Entry<K,V> lastEntry() {
2987      -            return isDescending? lowestEntry() : highestEntry();
     2982 +            return isDescending ? lowestEntry() : highestEntry();
2988 2983          }
2989 2984  
2990 2985          public Map.Entry<K,V> pollFirstEntry() {
2991      -            return isDescending? removeHighest() : removeLowest();
     2986 +            return isDescending ? removeHighest() : removeLowest();
2992 2987          }
2993 2988  
2994 2989          public Map.Entry<K,V> pollLastEntry() {
2995      -            return isDescending? removeLowest() : removeHighest();
     2990 +            return isDescending ? removeLowest() : removeHighest();
2996 2991          }
2997 2992  
2998 2993          /* ---------------- Submap Views -------------- */
2999 2994  
3000 2995          public NavigableSet<K> keySet() {
3001 2996              KeySet<K> ks = keySetView;
3002 2997              return (ks != null) ? ks : (keySetView = new KeySet(this));
3003 2998          }
3004 2999  
3005 3000          public NavigableSet<K> navigableKeySet() {
↓ open down ↓ 128 lines elided ↑ open up ↑
3134 3129  
3135 3130          final class SubMapEntryIterator extends SubMapIter<Map.Entry<K,V>> {
3136 3131              public Map.Entry<K,V> next() {
3137 3132                  Node<K,V> n = next;
3138 3133                  V v = nextValue;
3139 3134                  advance();
3140 3135                  return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
3141 3136              }
3142 3137          }
3143 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 +
3144 3157  }
    
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX