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