| 16 |
|
* <p>This class implements a concurrent variant of <a |
| 17 |
|
* href="http://en.wikipedia.org/wiki/Skip_list" target="_top">SkipLists</a> |
| 18 |
|
* providing expected average <i>log(n)</i> time cost for the |
| 19 |
< |
* <tt>containsKey</tt>, <tt>get</tt>, <tt>put</tt> and |
| 20 |
< |
* <tt>remove</tt> operations and their variants. Insertion, removal, |
| 19 |
> |
* {@code containsKey}, {@code get}, {@code put} and |
| 20 |
> |
* {@code remove} operations and their variants. Insertion, removal, |
| 21 |
|
* update, and access operations safely execute concurrently by |
| 22 |
|
* multiple threads. Iterators are <i>weakly consistent</i>, returning |
| 23 |
|
* elements reflecting the state of the map at some point at or since |
| 26 |
|
* other operations. Ascending key ordered views and their iterators |
| 27 |
|
* are faster than descending ones. |
| 28 |
|
* |
| 29 |
< |
* <p>All <tt>Map.Entry</tt> pairs returned by methods in this class |
| 29 |
> |
* <p>All {@code Map.Entry} pairs returned by methods in this class |
| 30 |
|
* and its views represent snapshots of mappings at the time they were |
| 31 |
< |
* produced. They do <em>not</em> support the <tt>Entry.setValue</tt> |
| 31 |
> |
* produced. They do <em>not</em> support the {@code Entry.setValue} |
| 32 |
|
* method. (Note however that it is possible to change mappings in the |
| 33 |
< |
* associated map using <tt>put</tt>, <tt>putIfAbsent</tt>, or |
| 34 |
< |
* <tt>replace</tt>, depending on exactly which effect you need.) |
| 33 |
> |
* associated map using {@code put}, {@code putIfAbsent}, or |
| 34 |
> |
* {@code replace}, depending on exactly which effect you need.) |
| 35 |
|
* |
| 36 |
< |
* <p>Beware that, unlike in most collections, the <tt>size</tt> |
| 36 |
> |
* <p>Beware that, unlike in most collections, the {@code size} |
| 37 |
|
* method is <em>not</em> a constant-time operation. Because of the |
| 38 |
|
* asynchronous nature of these maps, determining the current number |
| 39 |
|
* of elements requires a traversal of the elements, and so may report |
| 40 |
|
* inaccurate results if this collection is modified during traversal. |
| 41 |
< |
* Additionally, the bulk operations <tt>putAll</tt>, <tt>equals</tt>, |
| 42 |
< |
* <tt>toArray</tt>, <tt>containsValue</tt>, and <tt>clear</tt> are |
| 41 |
> |
* Additionally, the bulk operations {@code putAll}, {@code equals}, |
| 42 |
> |
* {@code toArray}, {@code containsValue}, and {@code clear} are |
| 43 |
|
* <em>not</em> guaranteed to be performed atomically. For example, an |
| 44 |
< |
* iterator operating concurrently with a <tt>putAll</tt> operation |
| 44 |
> |
* iterator operating concurrently with a {@code putAll} operation |
| 45 |
|
* might view only some of the added elements. |
| 46 |
|
* |
| 47 |
|
* <p>This class and its views and iterators implement all of the |
| 48 |
|
* <em>optional</em> methods of the {@link Map} and {@link Iterator} |
| 49 |
|
* interfaces. Like most other concurrent collections, this class does |
| 50 |
< |
* <em>not</em> permit the use of <tt>null</tt> keys or values because some |
| 50 |
> |
* <em>not</em> permit the use of {@code null} keys or values because some |
| 51 |
|
* null return values cannot be reliably distinguished from the absence of |
| 52 |
|
* elements. |
| 53 |
|
* |
| 1360 |
|
* comparator. |
| 1361 |
|
* |
| 1362 |
|
* @param comparator the comparator that will be used to order this map. |
| 1363 |
< |
* If <tt>null</tt>, the {@linkplain Comparable natural |
| 1363 |
> |
* If {@code null}, the {@linkplain Comparable natural |
| 1364 |
|
* ordering} of the keys will be used. |
| 1365 |
|
*/ |
| 1366 |
|
public ConcurrentSkipListMap(Comparator<? super K> comparator) { |
| 1374 |
|
* the keys. |
| 1375 |
|
* |
| 1376 |
|
* @param m the map whose mappings are to be placed in this map |
| 1377 |
< |
* @throws ClassCastException if the keys in <tt>m</tt> are not |
| 1377 |
> |
* @throws ClassCastException if the keys in {@code m} are not |
| 1378 |
|
* {@link Comparable}, or are not mutually comparable |
| 1379 |
|
* @throws NullPointerException if the specified map or any of its keys |
| 1380 |
|
* or values are null |
| 1401 |
|
} |
| 1402 |
|
|
| 1403 |
|
/** |
| 1404 |
< |
* Returns a shallow copy of this <tt>ConcurrentSkipListMap</tt> |
| 1404 |
> |
* Returns a shallow copy of this {@code ConcurrentSkipListMap} |
| 1405 |
|
* instance. (The keys and values themselves are not cloned.) |
| 1406 |
|
* |
| 1407 |
|
* @return a shallow copy of this map |
| 1482 |
|
* |
| 1483 |
|
* @serialData The key (Object) and value (Object) for each |
| 1484 |
|
* key-value mapping represented by the map, followed by |
| 1485 |
< |
* <tt>null</tt>. The key-value mappings are emitted in key-order |
| 1485 |
> |
* {@code null}. The key-value mappings are emitted in key-order |
| 1486 |
|
* (as determined by the Comparator, or by the keys' natural |
| 1487 |
|
* ordering if no Comparator). |
| 1488 |
|
*/ |
| 1566 |
|
/* ------ Map API methods ------ */ |
| 1567 |
|
|
| 1568 |
|
/** |
| 1569 |
< |
* Returns <tt>true</tt> if this map contains a mapping for the specified |
| 1569 |
> |
* Returns {@code true} if this map contains a mapping for the specified |
| 1570 |
|
* key. |
| 1571 |
|
* |
| 1572 |
|
* @param key key whose presence in this map is to be tested |
| 1573 |
< |
* @return <tt>true</tt> if this map contains a mapping for the specified key |
| 1573 |
> |
* @return {@code true} if this map contains a mapping for the specified key |
| 1574 |
|
* @throws ClassCastException if the specified key cannot be compared |
| 1575 |
|
* with the keys currently in the map |
| 1576 |
|
* @throws NullPointerException if the specified key is null |
| 1605 |
|
* @param key key with which the specified value is to be associated |
| 1606 |
|
* @param value value to be associated with the specified key |
| 1607 |
|
* @return the previous value associated with the specified key, or |
| 1608 |
< |
* <tt>null</tt> if there was no mapping for the key |
| 1608 |
> |
* {@code null} if there was no mapping for the key |
| 1609 |
|
* @throws ClassCastException if the specified key cannot be compared |
| 1610 |
|
* with the keys currently in the map |
| 1611 |
|
* @throws NullPointerException if the specified key or value is null |
| 1621 |
|
* |
| 1622 |
|
* @param key key for which mapping should be removed |
| 1623 |
|
* @return the previous value associated with the specified key, or |
| 1624 |
< |
* <tt>null</tt> if there was no mapping for the key |
| 1624 |
> |
* {@code null} if there was no mapping for the key |
| 1625 |
|
* @throws ClassCastException if the specified key cannot be compared |
| 1626 |
|
* with the keys currently in the map |
| 1627 |
|
* @throws NullPointerException if the specified key is null |
| 1631 |
|
} |
| 1632 |
|
|
| 1633 |
|
/** |
| 1634 |
< |
* Returns <tt>true</tt> if this map maps one or more keys to the |
| 1634 |
> |
* Returns {@code true} if this map maps one or more keys to the |
| 1635 |
|
* specified value. This operation requires time linear in the |
| 1636 |
|
* map size. Additionally, it is possible for the map to change |
| 1637 |
|
* during execution of this method, in which case the returned |
| 1638 |
|
* result may be inaccurate. |
| 1639 |
|
* |
| 1640 |
|
* @param value value whose presence in this map is to be tested |
| 1641 |
< |
* @return <tt>true</tt> if a mapping to <tt>value</tt> exists; |
| 1642 |
< |
* <tt>false</tt> otherwise |
| 1641 |
> |
* @return {@code true} if a mapping to {@code value} exists; |
| 1642 |
> |
* {@code false} otherwise |
| 1643 |
|
* @throws NullPointerException if the specified value is null |
| 1644 |
|
*/ |
| 1645 |
|
public boolean containsValue(Object value) { |
| 1655 |
|
|
| 1656 |
|
/** |
| 1657 |
|
* Returns the number of key-value mappings in this map. If this map |
| 1658 |
< |
* contains more than <tt>Integer.MAX_VALUE</tt> elements, it |
| 1659 |
< |
* returns <tt>Integer.MAX_VALUE</tt>. |
| 1658 |
> |
* contains more than {@code Integer.MAX_VALUE} elements, it |
| 1659 |
> |
* returns {@code Integer.MAX_VALUE}. |
| 1660 |
|
* |
| 1661 |
|
* <p>Beware that, unlike in most collections, this method is |
| 1662 |
|
* <em>NOT</em> a constant-time operation. Because of the |
| 1679 |
|
} |
| 1680 |
|
|
| 1681 |
|
/** |
| 1682 |
< |
* Returns <tt>true</tt> if this map contains no key-value mappings. |
| 1683 |
< |
* @return <tt>true</tt> if this map contains no key-value mappings |
| 1682 |
> |
* Returns {@code true} if this map contains no key-value mappings. |
| 1683 |
> |
* @return {@code true} if this map contains no key-value mappings |
| 1684 |
|
*/ |
| 1685 |
|
public boolean isEmpty() { |
| 1686 |
|
return findFirst() == null; |
| 1742 |
|
* The collection is backed by the map, so changes to the map are |
| 1743 |
|
* reflected in the collection, and vice-versa. The collection |
| 1744 |
|
* supports element removal, which removes the corresponding |
| 1745 |
< |
* mapping from the map, via the <tt>Iterator.remove</tt>, |
| 1746 |
< |
* <tt>Collection.remove</tt>, <tt>removeAll</tt>, |
| 1747 |
< |
* <tt>retainAll</tt> and <tt>clear</tt> operations. It does not |
| 1748 |
< |
* support the <tt>add</tt> or <tt>addAll</tt> operations. |
| 1745 |
> |
* mapping from the map, via the {@code Iterator.remove}, |
| 1746 |
> |
* {@code Collection.remove}, {@code removeAll}, |
| 1747 |
> |
* {@code retainAll} and {@code clear} operations. It does not |
| 1748 |
> |
* support the {@code add} or {@code addAll} operations. |
| 1749 |
|
* |
| 1750 |
< |
* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator |
| 1750 |
> |
* <p>The view's {@code iterator} is a "weakly consistent" iterator |
| 1751 |
|
* that will never throw {@link ConcurrentModificationException}, |
| 1752 |
|
* and guarantees to traverse elements as they existed upon |
| 1753 |
|
* construction of the iterator, and may (but is not guaranteed to) |
| 1764 |
|
* The set is backed by the map, so changes to the map are |
| 1765 |
|
* reflected in the set, and vice-versa. The set supports element |
| 1766 |
|
* removal, which removes the corresponding mapping from the map, |
| 1767 |
< |
* via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, |
| 1768 |
< |
* <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt> |
| 1769 |
< |
* operations. It does not support the <tt>add</tt> or |
| 1770 |
< |
* <tt>addAll</tt> operations. |
| 1767 |
> |
* via the {@code Iterator.remove}, {@code Set.remove}, |
| 1768 |
> |
* {@code removeAll}, {@code retainAll} and {@code clear} |
| 1769 |
> |
* operations. It does not support the {@code add} or |
| 1770 |
> |
* {@code addAll} operations. |
| 1771 |
|
* |
| 1772 |
< |
* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator |
| 1772 |
> |
* <p>The view's {@code iterator} is a "weakly consistent" iterator |
| 1773 |
|
* that will never throw {@link ConcurrentModificationException}, |
| 1774 |
|
* and guarantees to traverse elements as they existed upon |
| 1775 |
|
* construction of the iterator, and may (but is not guaranteed to) |
| 1776 |
|
* reflect any modifications subsequent to construction. |
| 1777 |
|
* |
| 1778 |
< |
* <p>The <tt>Map.Entry</tt> elements returned by |
| 1779 |
< |
* <tt>iterator.next()</tt> do <em>not</em> support the |
| 1780 |
< |
* <tt>setValue</tt> operation. |
| 1778 |
> |
* <p>The {@code Map.Entry} elements returned by |
| 1779 |
> |
* {@code iterator.next()} do <em>not</em> support the |
| 1780 |
> |
* {@code setValue} operation. |
| 1781 |
|
* |
| 1782 |
|
* @return a set view of the mappings contained in this map, |
| 1783 |
|
* sorted in ascending key order |
| 1801 |
|
|
| 1802 |
|
/** |
| 1803 |
|
* Compares the specified object with this map for equality. |
| 1804 |
< |
* Returns <tt>true</tt> if the given object is also a map and the |
| 1804 |
> |
* Returns {@code true} if the given object is also a map and the |
| 1805 |
|
* two maps represent the same mappings. More formally, two maps |
| 1806 |
< |
* <tt>m1</tt> and <tt>m2</tt> represent the same mappings if |
| 1807 |
< |
* <tt>m1.entrySet().equals(m2.entrySet())</tt>. This |
| 1806 |
> |
* {@code m1} and {@code m2} represent the same mappings if |
| 1807 |
> |
* {@code m1.entrySet().equals(m2.entrySet())}. This |
| 1808 |
|
* operation may return misleading results if either map is |
| 1809 |
|
* concurrently modified during execution of this method. |
| 1810 |
|
* |
| 1811 |
|
* @param o object to be compared for equality with this map |
| 1812 |
< |
* @return <tt>true</tt> if the specified object is equal to this map |
| 1812 |
> |
* @return {@code true} if the specified object is equal to this map |
| 1813 |
|
*/ |
| 1814 |
|
public boolean equals(Object o) { |
| 1815 |
|
if (o == this) |
| 1841 |
|
* {@inheritDoc} |
| 1842 |
|
* |
| 1843 |
|
* @return the previous value associated with the specified key, |
| 1844 |
< |
* or <tt>null</tt> if there was no mapping for the key |
| 1844 |
> |
* or {@code null} if there was no mapping for the key |
| 1845 |
|
* @throws ClassCastException if the specified key cannot be compared |
| 1846 |
|
* with the keys currently in the map |
| 1847 |
|
* @throws NullPointerException if the specified key or value is null |
| 1896 |
|
* {@inheritDoc} |
| 1897 |
|
* |
| 1898 |
|
* @return the previous value associated with the specified key, |
| 1899 |
< |
* or <tt>null</tt> if there was no mapping for the key |
| 1899 |
> |
* or {@code null} if there was no mapping for the key |
| 1900 |
|
* @throws ClassCastException if the specified key cannot be compared |
| 1901 |
|
* with the keys currently in the map |
| 1902 |
|
* @throws NullPointerException if the specified key or value is null |
| 2013 |
|
|
| 2014 |
|
/** |
| 2015 |
|
* Returns a key-value mapping associated with the greatest key |
| 2016 |
< |
* strictly less than the given key, or <tt>null</tt> if there is |
| 2016 |
> |
* strictly less than the given key, or {@code null} if there is |
| 2017 |
|
* no such key. The returned entry does <em>not</em> support the |
| 2018 |
< |
* <tt>Entry.setValue</tt> method. |
| 2018 |
> |
* {@code Entry.setValue} method. |
| 2019 |
|
* |
| 2020 |
|
* @throws ClassCastException {@inheritDoc} |
| 2021 |
|
* @throws NullPointerException if the specified key is null |
| 2035 |
|
|
| 2036 |
|
/** |
| 2037 |
|
* Returns a key-value mapping associated with the greatest key |
| 2038 |
< |
* less than or equal to the given key, or <tt>null</tt> if there |
| 2038 |
> |
* less than or equal to the given key, or {@code null} if there |
| 2039 |
|
* is no such key. The returned entry does <em>not</em> support |
| 2040 |
< |
* the <tt>Entry.setValue</tt> method. |
| 2040 |
> |
* the {@code Entry.setValue} method. |
| 2041 |
|
* |
| 2042 |
|
* @param key the key |
| 2043 |
|
* @throws ClassCastException {@inheritDoc} |
| 2059 |
|
|
| 2060 |
|
/** |
| 2061 |
|
* Returns a key-value mapping associated with the least key |
| 2062 |
< |
* greater than or equal to the given key, or <tt>null</tt> if |
| 2062 |
> |
* greater than or equal to the given key, or {@code null} if |
| 2063 |
|
* there is no such entry. The returned entry does <em>not</em> |
| 2064 |
< |
* support the <tt>Entry.setValue</tt> method. |
| 2064 |
> |
* support the {@code Entry.setValue} method. |
| 2065 |
|
* |
| 2066 |
|
* @throws ClassCastException {@inheritDoc} |
| 2067 |
|
* @throws NullPointerException if the specified key is null |
| 2081 |
|
|
| 2082 |
|
/** |
| 2083 |
|
* Returns a key-value mapping associated with the least key |
| 2084 |
< |
* strictly greater than the given key, or <tt>null</tt> if there |
| 2084 |
> |
* strictly greater than the given key, or {@code null} if there |
| 2085 |
|
* is no such key. The returned entry does <em>not</em> support |
| 2086 |
< |
* the <tt>Entry.setValue</tt> method. |
| 2086 |
> |
* the {@code Entry.setValue} method. |
| 2087 |
|
* |
| 2088 |
|
* @param key the key |
| 2089 |
|
* @throws ClassCastException {@inheritDoc} |
| 2105 |
|
|
| 2106 |
|
/** |
| 2107 |
|
* Returns a key-value mapping associated with the least |
| 2108 |
< |
* key in this map, or <tt>null</tt> if the map is empty. |
| 2108 |
> |
* key in this map, or {@code null} if the map is empty. |
| 2109 |
|
* The returned entry does <em>not</em> support |
| 2110 |
< |
* the <tt>Entry.setValue</tt> method. |
| 2110 |
> |
* the {@code Entry.setValue} method. |
| 2111 |
|
*/ |
| 2112 |
|
public Map.Entry<K,V> firstEntry() { |
| 2113 |
|
for (;;) { |
| 2122 |
|
|
| 2123 |
|
/** |
| 2124 |
|
* Returns a key-value mapping associated with the greatest |
| 2125 |
< |
* key in this map, or <tt>null</tt> if the map is empty. |
| 2125 |
> |
* key in this map, or {@code null} if the map is empty. |
| 2126 |
|
* The returned entry does <em>not</em> support |
| 2127 |
< |
* the <tt>Entry.setValue</tt> method. |
| 2127 |
> |
* the {@code Entry.setValue} method. |
| 2128 |
|
*/ |
| 2129 |
|
public Map.Entry<K,V> lastEntry() { |
| 2130 |
|
for (;;) { |
| 2139 |
|
|
| 2140 |
|
/** |
| 2141 |
|
* Removes and returns a key-value mapping associated with |
| 2142 |
< |
* the least key in this map, or <tt>null</tt> if the map is empty. |
| 2142 |
> |
* the least key in this map, or {@code null} if the map is empty. |
| 2143 |
|
* The returned entry does <em>not</em> support |
| 2144 |
< |
* the <tt>Entry.setValue</tt> method. |
| 2144 |
> |
* the {@code Entry.setValue} method. |
| 2145 |
|
*/ |
| 2146 |
|
public Map.Entry<K,V> pollFirstEntry() { |
| 2147 |
|
return doRemoveFirstEntry(); |
| 2149 |
|
|
| 2150 |
|
/** |
| 2151 |
|
* Removes and returns a key-value mapping associated with |
| 2152 |
< |
* the greatest key in this map, or <tt>null</tt> if the map is empty. |
| 2152 |
> |
* the greatest key in this map, or {@code null} if the map is empty. |
| 2153 |
|
* The returned entry does <em>not</em> support |
| 2154 |
< |
* the <tt>Entry.setValue</tt> method. |
| 2154 |
> |
* the {@code Entry.setValue} method. |
| 2155 |
|
*/ |
| 2156 |
|
public Map.Entry<K,V> pollLastEntry() { |
| 2157 |
|
return doRemoveLastEntry(); |
| 2437 |
|
* underlying maps, differing in that mappings outside their range are |
| 2438 |
|
* ignored, and attempts to add mappings outside their ranges result |
| 2439 |
|
* in {@link IllegalArgumentException}. Instances of this class are |
| 2440 |
< |
* constructed only using the <tt>subMap</tt>, <tt>headMap</tt>, and |
| 2441 |
< |
* <tt>tailMap</tt> methods of their underlying maps. |
| 2440 |
> |
* constructed only using the {@code subMap}, {@code headMap}, and |
| 2441 |
> |
* {@code tailMap} methods of their underlying maps. |
| 2442 |
|
* |
| 2443 |
|
* @serial include |
| 2444 |
|
*/ |
