ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/jsr166x/ConcurrentSkipListMap.java

Comparing jsr166/src/jsr166x/ConcurrentSkipListMap.java (file contents):
Revision 1.22 by jsr166, Sun Dec 30 02:11:59 2012 UTC vs.
Revision 1.23 by jsr166, Wed Jan 16 00:51:11 2013 UTC

#	Line 20 | Line 20 | import java.util.concurrent.atomic.*;
20		* <p>This class implements a concurrent variant of <a
21		* href="http://www.cs.umd.edu/~pugh/">SkipLists</a> providing
22		* expected average <i>log(n)</i> time cost for the
23	<	* <tt>containsKey</tt>, <tt>get</tt>, <tt>put</tt> and
24	<	* <tt>remove</tt> operations and their variants.  Insertion, removal,
23	>	* {@code containsKey}, {@code get}, {@code put} and
24	>	* {@code remove} operations and their variants.  Insertion, removal,
25		* update, and access operations safely execute concurrently by
26		* multiple threads. Iterators are <i>weakly consistent</i>, returning
27		* elements reflecting the state of the map at some point at or since
#	Line 30 | Line 30 | import java.util.concurrent.atomic.*;
30		* other operations. Ascending key ordered views and their iterators
31		* are faster than descending ones.
32		*
33	<	* <p>All <tt>Map.Entry</tt> pairs returned by methods in this class
33	>	* <p>All {@code Map.Entry} pairs returned by methods in this class
34		* and its views represent snapshots of mappings at the time they were
35	<	* produced. They do <em>not</em> support the <tt>Entry.setValue</tt>
35	>	* produced. They do <em>not</em> support the {@code Entry.setValue}
36		* method. (Note however that it is possible to change mappings in the
37	<	* associated map using <tt>put</tt>, <tt>putIfAbsent</tt>, or
38	<	* <tt>replace</tt>, depending on exactly which effect you need.)
37	>	* associated map using {@code put}, {@code putIfAbsent}, or
38	>	* {@code replace}, depending on exactly which effect you need.)
39		*
40	<	* <p>Beware that, unlike in most collections, the <tt>size</tt>
40	>	* <p>Beware that, unlike in most collections, the {@code size}
41		* method is <em>not</em> a constant-time operation. Because of the
42		* asynchronous nature of these maps, determining the current number
43		* of elements requires a traversal of the elements.  Additionally,
44	<	* the bulk operations <tt>putAll</tt>, <tt>equals</tt>, and
45	<	* <tt>clear</tt> are <em>not</em> guaranteed to be performed
44	>	* the bulk operations {@code putAll}, {@code equals}, and
45	>	* {@code clear} are <em>not</em> guaranteed to be performed
46		* atomically. For example, an iterator operating concurrently with a
47	<	* <tt>putAll</tt> operation might view only some of the added
47	>	* {@code putAll} operation might view only some of the added
48		* elements.
49		*
50		* <p>This class and its views and iterators implement all of the
51		* <em>optional</em> methods of the {@link Map} and {@link Iterator}
52		* interfaces. Like most other concurrent collections, this class does
53	<	* not permit the use of <tt>null</tt> keys or values because some
53	>	* not permit the use of {@code null} keys or values because some
54		* null return values cannot be reliably distinguished from the
55		* absence of elements.
56		*
#	Line 580 | Line 580 | public class ConcurrentSkipListMap<K,V>
580		/**
581		* An immutable representation of a key-value mapping as it
582		* existed at some point in time. This class does <em>not</em>
583	<	* support the <tt>Map.Entry.setValue</tt> method.
583	>	* support the {@code Map.Entry.setValue} method.
584		*/
585		static class SnapshotEntry<K,V> implements Map.Entry<K,V> {
586		private final K key;
#	Line 615 | Line 615 | public class ConcurrentSkipListMap<K,V>
615		}
616
617		/**
618	<	* Always fails, throwing <tt>UnsupportedOperationException</tt>.
618	>	* Always fails, throwing {@code UnsupportedOperationException}.
619		* @throws UnsupportedOperationException always
620		*/
621		public V setValue(V value) {
#	Line 644 | Line 644 | public class ConcurrentSkipListMap<K,V>
644
645		/**
646		* Returns a String consisting of the key followed by an
647	<	* equals sign (<tt>"="</tt>) followed by the associated
647	>	* equals sign ({@code "="}) followed by the associated
648		* value.
649		* @return a String representation of this entry
650		*/
#	Line 1473 | Line 1473 | public class ConcurrentSkipListMap<K,V>
1473		}
1474
1475		/**
1476	<	* Returns ceiling, or first node if key is <tt>null</tt>.
1476	>	* Returns ceiling, or first node if key is {@code null}.
1477		*/
1478		Node<K,V> findCeiling(K key) {
1479		return (key == null) ? findFirst() : findNear(key, GT|EQ);
1480		}
1481
1482		/**
1483	<	* Returns lower node, or last node if key is <tt>null</tt>.
1483	>	* Returns lower node, or last node if key is {@code null}.
1484		*/
1485		Node<K,V> findLower(K key) {
1486		return (key == null) ? findLast() : findNear(key, LT);
#	Line 1494 | Line 1494 | public class ConcurrentSkipListMap<K,V>
1494		* @param least minimum allowed key value
1495		* @param fence key greater than maximum allowed key value
1496		* @param keyOnly if true return key, else return SnapshotEntry
1497	<	* @return Key or Entry fitting relation, or <tt>null</tt> if no such
1497	>	* @return Key or Entry fitting relation, or {@code null} if no such
1498		*/
1499		Object getNear(K kkey, int rel, K least, K fence, boolean keyOnly) {
1500		K key = kkey;
#	Line 1522 | Line 1522 | public class ConcurrentSkipListMap<K,V>
1522		* @param least minimum allowed key value
1523		* @param fence key greater than maximum allowed key value
1524		* @param keyOnly if true return key, else return SnapshotEntry
1525	<	* @return least Key or Entry, or <tt>null</tt> if no such
1525	>	* @return least Key or Entry, or {@code null} if no such
1526		*/
1527		Object removeFirstEntryOfSubrange(K least, K fence, boolean keyOnly) {
1528		for (;;) {
#	Line 1543 | Line 1543 | public class ConcurrentSkipListMap<K,V>
1543		* @param least minimum allowed key value
1544		* @param fence key greater than maximum allowed key value
1545		* @param keyOnly if true return key, else return SnapshotEntry
1546	<	* @return least Key or Entry, or <tt>null</tt> if no such
1546	>	* @return least Key or Entry, or {@code null} if no such
1547		*/
1548		Object removeLastEntryOfSubrange(K least, K fence, boolean keyOnly) {
1549		for (;;) {
#	Line 1574 | Line 1574 | public class ConcurrentSkipListMap<K,V>
1574		* Constructs a new empty map, sorted according to the given comparator.
1575		*
1576		* @param c the comparator that will be used to sort this map.  A
1577	<	*        <tt>null</tt> value indicates that the keys' <i>natural
1577	>	*        {@code null} value indicates that the keys' <i>natural
1578		*        ordering</i> should be used.
1579		*/
1580		public ConcurrentSkipListMap(Comparator<? super K> c) {
#	Line 1589 | Line 1589 | public class ConcurrentSkipListMap<K,V>
1589		* @param  m the map whose mappings are to be placed in this map
1590		* @throws ClassCastException if the keys in m are not Comparable, or
1591		*         are not mutually comparable
1592	<	* @throws NullPointerException if the specified map is <tt>null</tt>
1592	>	* @throws NullPointerException if the specified map is {@code null}
1593		*/
1594		public ConcurrentSkipListMap(Map<? extends K, ? extends V> m) {
1595		this.comparator = null;
#	Line 1599 | Line 1599 | public class ConcurrentSkipListMap<K,V>
1599
1600		/**
1601		* Constructs a new map containing the same mappings as the given
1602	<	* <tt>SortedMap</tt>, sorted according to the same ordering.
1602	>	* {@code SortedMap}, sorted according to the same ordering.
1603		* @param m the sorted map whose mappings are to be placed in this
1604		* map, and whose comparator is to be used to sort this map.
1605		* @throws NullPointerException if the specified sorted map is
1606	<	* <tt>null</tt>.
1606	>	* {@code null}.
1607		*/
1608		public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) {
1609		this.comparator = m.comparator();
#	Line 1612 | Line 1612 | public class ConcurrentSkipListMap<K,V>
1612		}
1613
1614		/**
1615	<	* Returns a shallow copy of this <tt>Map</tt> instance. (The keys and
1615	>	* Returns a shallow copy of this {@code Map} instance. (The keys and
1616		* values themselves are not cloned.)
1617		*
1618		* @return a shallow copy of this Map
#	Line 1689 | Line 1689 | public class ConcurrentSkipListMap<K,V>
1689		/* ---------------- Serialization -------------- */
1690
1691		/**
1692	<	* Saves the state of the <tt>Map</tt> instance to a stream.
1692	>	* Saves the state of the {@code Map} instance to a stream.
1693		*
1694		* @serialData The key (Object) and value (Object) for each
1695		* key-value mapping represented by the Map, followed by
1696	<	* <tt>null</tt>. The key-value mappings are emitted in key-order
1696	>	* {@code null}. The key-value mappings are emitted in key-order
1697		* (as determined by the Comparator, or by the keys' natural
1698		* ordering if no Comparator).
1699		*/
#	Line 1714 | Line 1714 | public class ConcurrentSkipListMap<K,V>
1714		}
1715
1716		/**
1717	<	* Reconstitutes the <tt>Map</tt> instance from a stream.
1717	>	* Reconstitutes the {@code Map} instance from a stream.
1718		*/
1719		private void readObject(final java.io.ObjectInputStream s)
1720		throws java.io.IOException, ClassNotFoundException {
#	Line 1777 | Line 1777 | public class ConcurrentSkipListMap<K,V>
1777		/* ------ Map API methods ------ */
1778
1779		/**
1780	<	* Returns <tt>true</tt> if this map contains a mapping for the specified
1780	>	* Returns {@code true} if this map contains a mapping for the specified
1781		* key.
1782		* @param key key whose presence in this map is to be tested
1783	<	* @return <tt>true</tt> if this map contains a mapping for the
1783	>	* @return {@code true} if this map contains a mapping for the
1784		*            specified key
1785		* @throws ClassCastException if the key cannot be compared with the keys
1786		*                  currently in the map
1787	<	* @throws NullPointerException if the key is <tt>null</tt>
1787	>	* @throws NullPointerException if the key is {@code null}
1788		*/
1789		public boolean containsKey(Object key) {
1790		return doGet(key) != null;
#	Line 1792 | Line 1792 | public class ConcurrentSkipListMap<K,V>
1792
1793		/**
1794		* Returns the value to which this map maps the specified key.  Returns
1795	<	* <tt>null</tt> if the map contains no mapping for this key.
1795	>	* {@code null} if the map contains no mapping for this key.
1796		*
1797		* @param key key whose associated value is to be returned
1798		* @return the value to which this map maps the specified key, or
1799	<	*               <tt>null</tt> if the map contains no mapping for the key
1799	>	*               {@code null} if the map contains no mapping for the key
1800		* @throws ClassCastException if the key cannot be compared with the keys
1801		*                  currently in the map
1802	<	* @throws NullPointerException if the key is <tt>null</tt>
1802	>	* @throws NullPointerException if the key is {@code null}
1803		*/
1804		public V get(Object key) {
1805		return doGet(key);
#	Line 1813 | Line 1813 | public class ConcurrentSkipListMap<K,V>
1813		* @param key key with which the specified value is to be associated
1814		* @param value value to be associated with the specified key
1815		*
1816	<	* @return previous value associated with specified key, or <tt>null</tt>
1816	>	* @return previous value associated with specified key, or {@code null}
1817		*         if there was no mapping for key
1818		* @throws ClassCastException if the key cannot be compared with the keys
1819		*            currently in the map
1820	<	* @throws NullPointerException if the key or value are <tt>null</tt>
1820	>	* @throws NullPointerException if the key or value are {@code null}
1821		*/
1822		public V put(K key, V value) {
1823		if (value == null)
#	Line 1829 | Line 1829 | public class ConcurrentSkipListMap<K,V>
1829		* Removes the mapping for this key from this Map if present.
1830		*
1831		* @param  key key for which mapping should be removed
1832	<	* @return previous value associated with specified key, or <tt>null</tt>
1832	>	* @return previous value associated with specified key, or {@code null}
1833		*         if there was no mapping for key
1834		*
1835		* @throws ClassCastException if the key cannot be compared with the keys
1836		*            currently in the map
1837	<	* @throws NullPointerException if the key is <tt>null</tt>
1837	>	* @throws NullPointerException if the key is {@code null}
1838		*/
1839		public V remove(Object key) {
1840		return doRemove(key, null);
1841		}
1842
1843		/**
1844	<	* Returns <tt>true</tt> if this map maps one or more keys to the
1844	>	* Returns {@code true} if this map maps one or more keys to the
1845		* specified value.  This operation requires time linear in the
1846		* Map size.
1847		*
1848		* @param value value whose presence in this Map is to be tested
1849	<	* @return  <tt>true</tt> if a mapping to <tt>value</tt> exists;
1850	<	*          <tt>false</tt> otherwise
1851	<	* @throws  NullPointerException  if the value is <tt>null</tt>
1849	>	* @return  {@code true} if a mapping to {@code value} exists;
1850	>	*          {@code false} otherwise
1851	>	* @throws  NullPointerException  if the value is {@code null}
1852		*/
1853		public boolean containsValue(Object value) {
1854		if (value == null)
#	Line 1863 | Line 1863 | public class ConcurrentSkipListMap<K,V>
1863
1864		/**
1865		* Returns the number of elements in this map.  If this map
1866	<	* contains more than <tt>Integer.MAX_VALUE</tt> elements, it
1867	<	* returns <tt>Integer.MAX_VALUE</tt>.
1866	>	* contains more than {@code Integer.MAX_VALUE} elements, it
1867	>	* returns {@code Integer.MAX_VALUE}.
1868		*
1869		* <p>Beware that, unlike in most collections, this method is
1870		* <em>NOT</em> a constant-time operation. Because of the
#	Line 1887 | Line 1887 | public class ConcurrentSkipListMap<K,V>
1887		}
1888
1889		/**
1890	<	* Returns <tt>true</tt> if this map contains no key-value mappings.
1891	<	* @return <tt>true</tt> if this map contains no key-value mappings
1890	>	* Returns {@code true} if this map contains no key-value mappings.
1891	>	* @return {@code true} if this map contains no key-value mappings
1892		*/
1893		public boolean isEmpty() {
1894		return findFirst() == null;
#	Line 1905 | Line 1905 | public class ConcurrentSkipListMap<K,V>
1905		* Returns a set view of the keys contained in this map.  The set is
1906		* backed by the map, so changes to the map are reflected in the set, and
1907		* vice-versa.  The set supports element removal, which removes the
1908	<	* corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
1909	<	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
1910	<	* <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
1911	<	* <tt>addAll</tt> operations.
1912	<	* The view's <tt>iterator</tt> is a "weakly consistent" iterator that
1908	>	* corresponding mapping from this map, via the {@code Iterator.remove},
1909	>	* {@code Set.remove}, {@code removeAll}, {@code retainAll}, and
1910	>	* {@code clear} operations.  It does not support the {@code add} or
1911	>	* {@code addAll} operations.
1912	>	* The view's {@code iterator} is a "weakly consistent" iterator that
1913		* will never throw {@link java.util.ConcurrentModificationException},
1914		* and guarantees to traverse elements as they existed upon
1915		* construction of the iterator, and may (but is not guaranteed to)
#	Line 1936 | Line 1936 | public class ConcurrentSkipListMap<K,V>
1936		* descending order.  The set is backed by the map, so changes to
1937		* the map are reflected in the set, and vice-versa.  The set
1938		* supports element removal, which removes the corresponding
1939	<	* mapping from this map, via the <tt>Iterator.remove</tt>,
1940	<	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>,
1941	<	* and <tt>clear</tt> operations.  It does not support the
1942	<	* <tt>add</tt> or <tt>addAll</tt> operations.  The view's
1943	<	* <tt>iterator</tt> is a "weakly consistent" iterator that will
1939	>	* mapping from this map, via the {@code Iterator.remove},
1940	>	* {@code Set.remove}, {@code removeAll}, {@code retainAll},
1941	>	* and {@code clear} operations.  It does not support the
1942	>	* {@code add} or {@code addAll} operations.  The view's
1943	>	* {@code iterator} is a "weakly consistent" iterator that will
1944		* never throw {@link java.util.ConcurrentModificationException},
1945		* and guarantees to traverse elements as they existed upon
1946		* construction of the iterator, and may (but is not guaranteed
#	Line 1967 | Line 1967 | public class ConcurrentSkipListMap<K,V>
1967		* The collection is backed by the map, so changes to the map are
1968		* reflected in the collection, and vice-versa.  The collection
1969		* supports element removal, which removes the corresponding
1970	<	* mapping from this map, via the <tt>Iterator.remove</tt>,
1971	<	* <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1972	<	* <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does not
1973	<	* support the <tt>add</tt> or <tt>addAll</tt> operations.  The
1974	<	* view's <tt>iterator</tt> is a "weakly consistent" iterator that
1970	>	* mapping from this map, via the {@code Iterator.remove},
1971	>	* {@code Collection.remove}, {@code removeAll},
1972	>	* {@code retainAll}, and {@code clear} operations.  It does not
1973	>	* support the {@code add} or {@code addAll} operations.  The
1974	>	* view's {@code iterator} is a "weakly consistent" iterator that
1975		* will never throw {@link
1976		* java.util.ConcurrentModificationException}, and guarantees to
1977		* traverse elements as they existed upon construction of the
#	Line 1988 | Line 1988 | public class ConcurrentSkipListMap<K,V>
1988		/**
1989		* Returns a collection view of the mappings contained in this
1990		* map.  Each element in the returned collection is a
1991	<	* <tt>Map.Entry</tt>.  The collection is backed by the map, so
1991	>	* {@code Map.Entry}.  The collection is backed by the map, so
1992		* changes to the map are reflected in the collection, and
1993		* vice-versa.  The collection supports element removal, which
1994		* removes the corresponding mapping from the map, via the
1995	<	* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
1996	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1997	<	* operations.  It does not support the <tt>add</tt> or
1998	<	* <tt>addAll</tt> operations.  The view's <tt>iterator</tt> is a
1995	>	* {@code Iterator.remove}, {@code Collection.remove},
1996	>	* {@code removeAll}, {@code retainAll}, and {@code clear}
1997	>	* operations.  It does not support the {@code add} or
1998	>	* {@code addAll} operations.  The view's {@code iterator} is a
1999		* "weakly consistent" iterator that will never throw {@link
2000		* java.util.ConcurrentModificationException}, and guarantees to
2001		* traverse elements as they existed upon construction of the
2002		* iterator, and may (but is not guaranteed to) reflect any
2003		* modifications subsequent to construction. The
2004	<	* <tt>Map.Entry</tt> elements returned by
2005	<	* <tt>iterator.next()</tt> do <em>not</em> support the
2006	<	* <tt>setValue</tt> operation.
2004	>	* {@code Map.Entry} elements returned by
2005	>	* {@code iterator.next()} do <em>not</em> support the
2006	>	* {@code setValue} operation.
2007		*
2008		* @return a collection view of the mappings contained in this map
2009		*/
#	Line 2015 | Line 2015 | public class ConcurrentSkipListMap<K,V>
2015		/**
2016		* Returns a collection view of the mappings contained in this
2017		* map, in descending order.  Each element in the returned
2018	<	* collection is a <tt>Map.Entry</tt>.  The collection is backed
2018	>	* collection is a {@code Map.Entry}.  The collection is backed
2019		* by the map, so changes to the map are reflected in the
2020		* collection, and vice-versa.  The collection supports element
2021		* removal, which removes the corresponding mapping from the map,
2022	<	* via the <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
2023	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
2024	<	* operations.  It does not support the <tt>add</tt> or
2025	<	* <tt>addAll</tt> operations.  The view's <tt>iterator</tt> is a
2022	>	* via the {@code Iterator.remove}, {@code Collection.remove},
2023	>	* {@code removeAll}, {@code retainAll}, and {@code clear}
2024	>	* operations.  It does not support the {@code add} or
2025	>	* {@code addAll} operations.  The view's {@code iterator} is a
2026		* "weakly consistent" iterator that will never throw {@link
2027		* java.util.ConcurrentModificationException}, and guarantees to
2028		* traverse elements as they existed upon construction of the
2029		* iterator, and may (but is not guaranteed to) reflect any
2030		* modifications subsequent to construction. The
2031	<	* <tt>Map.Entry</tt> elements returned by
2032	<	* <tt>iterator.next()</tt> do <em>not</em> support the
2033	<	* <tt>setValue</tt> operation.
2031	>	* {@code Map.Entry} elements returned by
2032	>	* {@code iterator.next()} do <em>not</em> support the
2033	>	* {@code setValue} operation.
2034		*
2035		* @return a collection view of the mappings contained in this map
2036		*/
#	Line 2043 | Line 2043 | public class ConcurrentSkipListMap<K,V>
2043
2044		/**
2045		* Compares the specified object with this map for equality.
2046	<	* Returns <tt>true</tt> if the given object is also a map and the
2046	>	* Returns {@code true} if the given object is also a map and the
2047		* two maps represent the same mappings.  More formally, two maps
2048	<	* <tt>t1</tt> and <tt>t2</tt> represent the same mappings if
2049	<	* <tt>t1.keySet().equals(t2.keySet())</tt> and for every key
2050	<	* <tt>k</tt> in <tt>t1.keySet()</tt>, <tt> (t1.get(k)==null ?
2051	<	* t2.get(k)==null : t1.get(k).equals(t2.get(k))) </tt>.  This
2048	>	* {@code t1} and {@code t2} represent the same mappings if
2049	>	* {@code t1.keySet().equals(t2.keySet())} and for every key
2050	>	* {@code k} in {@code t1.keySet()}, {@code  (t1.get(k)==null ?
2051	>	* t2.get(k)==null : t1.get(k).equals(t2.get(k))) }.  This
2052		* operation may return misleading results if either map is
2053		* concurrently modified during execution of this method.
2054		*
2055		* @param o object to be compared for equality with this map
2056	<	* @return <tt>true</tt> if the specified object is equal to this map
2056	>	* @return {@code true} if the specified object is equal to this map
2057		*/
2058		public boolean equals(Object o) {
2059		if (o == this)
#	Line 2101 | Line 2101 | public class ConcurrentSkipListMap<K,V>
2101		* except that the action is performed atomically.
2102		* @param key key with which the specified value is to be associated
2103		* @param value value to be associated with the specified key
2104	<	* @return previous value associated with specified key, or <tt>null</tt>
2104	>	* @return previous value associated with specified key, or {@code null}
2105		*         if there was no mapping for key
2106		*
2107		* @throws ClassCastException if the key cannot be compared with the keys
2108		*            currently in the map
2109	<	* @throws NullPointerException if the key or value are <tt>null</tt>
2109	>	* @throws NullPointerException if the key or value are {@code null}
2110		*/
2111		public V putIfAbsent(K key, V value) {
2112		if (value == null)
#	Line 2129 | Line 2129 | public class ConcurrentSkipListMap<K,V>
2129		* @return true if the value was removed, false otherwise
2130		* @throws ClassCastException if the key cannot be compared with the keys
2131		*            currently in the map
2132	<	* @throws NullPointerException if the key or value are <tt>null</tt>
2132	>	* @throws NullPointerException if the key or value are {@code null}
2133		*/
2134		public boolean remove(Object key, Object value) {
2135		if (value == null)
#	Line 2154 | Line 2154 | public class ConcurrentSkipListMap<K,V>
2154		* @throws ClassCastException if the key cannot be compared with the keys
2155		*            currently in the map
2156		* @throws NullPointerException if key, oldValue or newValue are
2157	<	* <tt>null</tt>
2157	>	* {@code null}
2158		*/
2159		public boolean replace(K key, V oldValue, V newValue) {
2160		if (oldValue == null || newValue == null)
#	Line 2185 | Line 2185 | public class ConcurrentSkipListMap<K,V>
2185		* except that the action is performed atomically.
2186		* @param key key with which the specified value is associated
2187		* @param value value to be associated with the specified key
2188	<	* @return previous value associated with specified key, or <tt>null</tt>
2188	>	* @return previous value associated with specified key, or {@code null}
2189		*         if there was no mapping for key
2190		* @throws ClassCastException if the key cannot be compared with the keys
2191		*            currently in the map
2192	<	* @throws NullPointerException if the key or value are <tt>null</tt>
2192	>	* @throws NullPointerException if the key or value are {@code null}
2193		*/
2194		public V replace(K key, V value) {
2195		if (value == null)
#	Line 2208 | Line 2208 | public class ConcurrentSkipListMap<K,V>
2208		/* ------ SortedMap API methods ------ */
2209
2210		/**
2211	<	* Returns the comparator used to order this map, or <tt>null</tt>
2211	>	* Returns the comparator used to order this map, or {@code null}
2212		* if this map uses its keys' natural order.
2213		*
2214		* @return the comparator associated with this map, or
2215	<	* <tt>null</tt> if it uses its keys' natural sort method.
2215	>	* {@code null} if it uses its keys' natural sort method.
2216		*/
2217		public Comparator<? super K> comparator() {
2218		return comparator;
#	Line 2246 | Line 2246 | public class ConcurrentSkipListMap<K,V>
2246
2247		/**
2248		* Returns a view of the portion of this map whose keys range from
2249	<	* <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.  (If
2250	<	* <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned sorted map
2249	>	* {@code fromKey}, inclusive, to {@code toKey}, exclusive.  (If
2250	>	* {@code fromKey} and {@code toKey} are equal, the returned sorted map
2251		* is empty.)  The returned sorted map is backed by this map, so changes
2252		* in the returned sorted map are reflected in this map, and vice-versa.
2253		*
#	Line 2255 | Line 2255 | public class ConcurrentSkipListMap<K,V>
2255		* @param toKey high endpoint (exclusive) of the subMap
2256		*
2257		* @return a view of the portion of this map whose keys range from
2258	<	* <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive
2258	>	* {@code fromKey}, inclusive, to {@code toKey}, exclusive
2259		*
2260	<	* @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt>
2260	>	* @throws ClassCastException if {@code fromKey} and {@code toKey}
2261		*         cannot be compared to one another using this map's comparator
2262		*         (or, if the map has no comparator, using natural ordering)
2263	<	* @throws IllegalArgumentException if <tt>fromKey</tt> is greater than
2264	<	*         <tt>toKey</tt>
2265	<	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
2266	<	*               <tt>null</tt>
2263	>	* @throws IllegalArgumentException if {@code fromKey} is greater than
2264	>	*         {@code toKey}
2265	>	* @throws NullPointerException if {@code fromKey} or {@code toKey} is
2266	>	*               {@code null}
2267		*/
2268		public ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey) {
2269		if (fromKey == null || toKey == null)
#	Line 2273 | Line 2273 | public class ConcurrentSkipListMap<K,V>
2273
2274		/**
2275		* Returns a view of the portion of this map whose keys are
2276	<	* strictly less than <tt>toKey</tt>.  The returned sorted map is
2276	>	* strictly less than {@code toKey}.  The returned sorted map is
2277		* backed by this map, so changes in the returned sorted map are
2278		* reflected in this map, and vice-versa.
2279		* @param toKey high endpoint (exclusive) of the headMap
2280		* @return a view of the portion of this map whose keys are
2281	<	* strictly less than <tt>toKey</tt>
2281	>	* strictly less than {@code toKey}
2282		*
2283	<	* @throws ClassCastException if <tt>toKey</tt> is not compatible
2283	>	* @throws ClassCastException if {@code toKey} is not compatible
2284		* with this map's comparator (or, if the map has no comparator,
2285	<	* if <tt>toKey</tt> does not implement <tt>Comparable</tt>)
2286	<	* @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt>
2285	>	* if {@code toKey} does not implement {@code Comparable})
2286	>	* @throws NullPointerException if {@code toKey} is {@code null}
2287		*/
2288		public ConcurrentNavigableMap<K,V> headMap(K toKey) {
2289		if (toKey == null)
#	Line 2293 | Line 2293 | public class ConcurrentSkipListMap<K,V>
2293
2294		/**
2295		* Returns a view of the portion of this map whose keys are
2296	<	* greater than or equal to <tt>fromKey</tt>.  The returned sorted
2296	>	* greater than or equal to {@code fromKey}.  The returned sorted
2297		* map is backed by this map, so changes in the returned sorted
2298		* map are reflected in this map, and vice-versa.
2299		* @param fromKey low endpoint (inclusive) of the tailMap
2300		* @return a view of the portion of this map whose keys are
2301	<	* greater than or equal to <tt>fromKey</tt>
2302	<	* @throws ClassCastException if <tt>fromKey</tt> is not
2301	>	* greater than or equal to {@code fromKey}
2302	>	* @throws ClassCastException if {@code fromKey} is not
2303		* compatible with this map's comparator (or, if the map has no
2304	<	* comparator, if <tt>fromKey</tt> does not implement
2305	<	* <tt>Comparable</tt>)
2306	<	* @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt>
2304	>	* comparator, if {@code fromKey} does not implement
2305	>	* {@code Comparable})
2306	>	* @throws NullPointerException if {@code fromKey} is {@code null}
2307		*/
2308		public ConcurrentNavigableMap<K,V> tailMap(K fromKey) {
2309		if (fromKey == null)
#	Line 2315 | Line 2315 | public class ConcurrentSkipListMap<K,V>
2315
2316		/**
2317		* Returns a key-value mapping associated with the least key
2318	<	* greater than or equal to the given key, or <tt>null</tt> if
2318	>	* greater than or equal to the given key, or {@code null} if
2319		* there is no such entry. The returned entry does <em>not</em>
2320	<	* support the <tt>Entry.setValue</tt> method.
2320	>	* support the {@code Entry.setValue} method.
2321		*
2322		* @param key the key
2323		* @return an Entry associated with ceiling of given key, or
2324	<	* <tt>null</tt> if there is no such Entry
2324	>	* {@code null} if there is no such Entry
2325		* @throws ClassCastException if key cannot be compared with the
2326		* keys currently in the map
2327	<	* @throws NullPointerException if key is <tt>null</tt>
2327	>	* @throws NullPointerException if key is {@code null}
2328		*/
2329		public Map.Entry<K,V> ceilingEntry(K key) {
2330		return getNear(key, GT|EQ);
#	Line 2332 | Line 2332 | public class ConcurrentSkipListMap<K,V>
2332
2333		/**
2334		* Returns least key greater than or equal to the given key, or
2335	<	* <tt>null</tt> if there is no such key.
2335	>	* {@code null} if there is no such key.
2336		*
2337		* @param key the key
2338	<	* @return the ceiling key, or <tt>null</tt>
2338	>	* @return the ceiling key, or {@code null}
2339		* if there is no such key
2340		* @throws ClassCastException if key cannot be compared with the keys
2341		*            currently in the map
2342	<	* @throws NullPointerException if key is <tt>null</tt>
2342	>	* @throws NullPointerException if key is {@code null}
2343		*/
2344		public K ceilingKey(K key) {
2345		Node<K,V> n = findNear(key, GT|EQ);
#	Line 2348 | Line 2348 | public class ConcurrentSkipListMap<K,V>
2348
2349		/**
2350		* Returns a key-value mapping associated with the greatest
2351	<	* key strictly less than the given key, or <tt>null</tt> if there is no
2351	>	* key strictly less than the given key, or {@code null} if there is no
2352		* such entry. The returned entry does <em>not</em> support
2353	<	* the <tt>Entry.setValue</tt> method.
2353	>	* the {@code Entry.setValue} method.
2354		*
2355		* @param key the key
2356		* @return an Entry with greatest key less than the given
2357	<	* key, or <tt>null</tt> if there is no such Entry
2357	>	* key, or {@code null} if there is no such Entry
2358		* @throws ClassCastException if key cannot be compared with the keys
2359		*            currently in the map
2360	<	* @throws NullPointerException if key is <tt>null</tt>
2360	>	* @throws NullPointerException if key is {@code null}
2361		*/
2362		public Map.Entry<K,V> lowerEntry(K key) {
2363		return getNear(key, LT);
#	Line 2365 | Line 2365 | public class ConcurrentSkipListMap<K,V>
2365
2366		/**
2367		* Returns the greatest key strictly less than the given key, or
2368	<	* <tt>null</tt> if there is no such key.
2368	>	* {@code null} if there is no such key.
2369		*
2370		* @param key the key
2371		* @return the greatest key less than the given
2372	<	* key, or <tt>null</tt> if there is no such key
2372	>	* key, or {@code null} if there is no such key
2373		* @throws ClassCastException if key cannot be compared with the keys
2374		*            currently in the map
2375	<	* @throws NullPointerException if key is <tt>null</tt>
2375	>	* @throws NullPointerException if key is {@code null}
2376		*/
2377		public K lowerKey(K key) {
2378		Node<K,V> n = findNear(key, LT);
#	Line 2381 | Line 2381 | public class ConcurrentSkipListMap<K,V>
2381
2382		/**
2383		* Returns a key-value mapping associated with the greatest key
2384	<	* less than or equal to the given key, or <tt>null</tt> if there
2384	>	* less than or equal to the given key, or {@code null} if there
2385		* is no such entry. The returned entry does <em>not</em> support
2386	<	* the <tt>Entry.setValue</tt> method.
2386	>	* the {@code Entry.setValue} method.
2387		*
2388		* @param key the key
2389	<	* @return an Entry associated with floor of given key, or <tt>null</tt>
2389	>	* @return an Entry associated with floor of given key, or {@code null}
2390		* if there is no such Entry
2391		* @throws ClassCastException if key cannot be compared with the keys
2392		*            currently in the map
2393	<	* @throws NullPointerException if key is <tt>null</tt>
2393	>	* @throws NullPointerException if key is {@code null}
2394		*/
2395		public Map.Entry<K,V> floorEntry(K key) {
2396		return getNear(key, LT|EQ);
#	Line 2398 | Line 2398 | public class ConcurrentSkipListMap<K,V>
2398
2399		/**
2400		* Returns the greatest key
2401	<	* less than or equal to the given key, or <tt>null</tt> if there
2401	>	* less than or equal to the given key, or {@code null} if there
2402		* is no such key.
2403		*
2404		* @param key the key
2405	<	* @return the floor of given key, or <tt>null</tt> if there is no
2405	>	* @return the floor of given key, or {@code null} if there is no
2406		* such key
2407		* @throws ClassCastException if key cannot be compared with the keys
2408		*            currently in the map
2409	<	* @throws NullPointerException if key is <tt>null</tt>
2409	>	* @throws NullPointerException if key is {@code null}
2410		*/
2411		public K floorKey(K key) {
2412		Node<K,V> n = findNear(key, LT|EQ);
#	Line 2415 | Line 2415 | public class ConcurrentSkipListMap<K,V>
2415
2416		/**
2417		* Returns a key-value mapping associated with the least key
2418	<	* strictly greater than the given key, or <tt>null</tt> if there
2418	>	* strictly greater than the given key, or {@code null} if there
2419		* is no such entry. The returned entry does <em>not</em> support
2420	<	* the <tt>Entry.setValue</tt> method.
2420	>	* the {@code Entry.setValue} method.
2421		*
2422		* @param key the key
2423		* @return an Entry with least key greater than the given key, or
2424	<	* <tt>null</tt> if there is no such Entry
2424	>	* {@code null} if there is no such Entry
2425		* @throws ClassCastException if key cannot be compared with the keys
2426		*            currently in the map
2427	<	* @throws NullPointerException if key is <tt>null</tt>
2427	>	* @throws NullPointerException if key is {@code null}
2428		*/
2429		public Map.Entry<K,V> higherEntry(K key) {
2430		return getNear(key, GT);
#	Line 2432 | Line 2432 | public class ConcurrentSkipListMap<K,V>
2432
2433		/**
2434		* Returns the least key strictly greater than the given key, or
2435	<	* <tt>null</tt> if there is no such key.
2435	>	* {@code null} if there is no such key.
2436		*
2437		* @param key the key
2438		* @return the least key greater than the given key, or
2439	<	* <tt>null</tt> if there is no such key
2439	>	* {@code null} if there is no such key
2440		* @throws ClassCastException if key cannot be compared with the keys
2441		*            currently in the map
2442	<	* @throws NullPointerException if key is <tt>null</tt>
2442	>	* @throws NullPointerException if key is {@code null}
2443		*/
2444		public K higherKey(K key) {
2445		Node<K,V> n = findNear(key, GT);
#	Line 2448 | Line 2448 | public class ConcurrentSkipListMap<K,V>
2448
2449		/**
2450		* Returns a key-value mapping associated with the least
2451	<	* key in this map, or <tt>null</tt> if the map is empty.
2451	>	* key in this map, or {@code null} if the map is empty.
2452		* The returned entry does <em>not</em> support
2453	<	* the <tt>Entry.setValue</tt> method.
2453	>	* the {@code Entry.setValue} method.
2454		*
2455	<	* @return an Entry with least key, or <tt>null</tt>
2455	>	* @return an Entry with least key, or {@code null}
2456		* if the map is empty
2457		*/
2458		public Map.Entry<K,V> firstEntry() {
#	Line 2468 | Line 2468 | public class ConcurrentSkipListMap<K,V>
2468
2469		/**
2470		* Returns a key-value mapping associated with the greatest
2471	<	* key in this map, or <tt>null</tt> if the map is empty.
2471	>	* key in this map, or {@code null} if the map is empty.
2472		* The returned entry does <em>not</em> support
2473	<	* the <tt>Entry.setValue</tt> method.
2473	>	* the {@code Entry.setValue} method.
2474		*
2475	<	* @return an Entry with greatest key, or <tt>null</tt>
2475	>	* @return an Entry with greatest key, or {@code null}
2476		* if the map is empty
2477		*/
2478		public Map.Entry<K,V> lastEntry() {
#	Line 2488 | Line 2488 | public class ConcurrentSkipListMap<K,V>
2488
2489		/**
2490		* Removes and returns a key-value mapping associated with
2491	<	* the least key in this map, or <tt>null</tt> if the map is empty.
2491	>	* the least key in this map, or {@code null} if the map is empty.
2492		* The returned entry does <em>not</em> support
2493	<	* the <tt>Entry.setValue</tt> method.
2493	>	* the {@code Entry.setValue} method.
2494		*
2495	<	* @return the removed first entry of this map, or <tt>null</tt>
2495	>	* @return the removed first entry of this map, or {@code null}
2496		* if the map is empty
2497		*/
2498		public Map.Entry<K,V> pollFirstEntry() {
#	Line 2501 | Line 2501 | public class ConcurrentSkipListMap<K,V>
2501
2502		/**
2503		* Removes and returns a key-value mapping associated with
2504	<	* the greatest key in this map, or <tt>null</tt> if the map is empty.
2504	>	* the greatest key in this map, or {@code null} if the map is empty.
2505		* The returned entry does <em>not</em> support
2506	<	* the <tt>Entry.setValue</tt> method.
2506	>	* the {@code Entry.setValue} method.
2507		*
2508	<	* @return the removed last entry of this map, or <tt>null</tt>
2508	>	* @return the removed last entry of this map, or {@code null}
2509		* if the map is empty
2510		*/
2511		public Map.Entry<K,V> pollLastEntry() {
#	Line 2548 | Line 2548 | public class ConcurrentSkipListMap<K,V>
2548
2549		/**
2550		* initialize ascending iterator starting at given least key,
2551	<	* or first node if least is <tt>null</tt>, but not greater or
2552	<	* equal to fence, or end if fence is <tt>null</tt>.
2551	>	* or first node if least is {@code null}, but not greater or
2552	>	* equal to fence, or end if fence is {@code null}.
2553		*/
2554		final void initAscending(K least, K fence) {
2555		for (;;) {
#	Line 2616 | Line 2616 | public class ConcurrentSkipListMap<K,V>
2616		/**
2617		* initialize descending iterator starting at key less
2618		* than or equal to given fence key, or
2619	<	* last node if fence is <tt>null</tt>, but not less than
2620	<	* least, or beginning if lest is <tt>null</tt>.
2619	>	* last node if fence is {@code null}, but not less than
2620	>	* least, or beginning if lest is {@code null}.
2621		*/
2622		final void initDescending(K least, K fence) {
2623		for (;;) {
#	Line 3025 | Line 3025 | public class ConcurrentSkipListMap<K,V>
3025		* underlying maps, differing in that mappings outside their range are
3026		* ignored, and attempts to add mappings outside their ranges result
3027		* in {@link IllegalArgumentException}.  Instances of this class are
3028	<	* constructed only using the <tt>subMap</tt>, <tt>headMap</tt>, and
3029	<	* <tt>tailMap</tt> methods of their underlying maps.
3028	>	* constructed only using the {@code subMap}, {@code headMap}, and
3029	>	* {@code tailMap} methods of their underlying maps.
3030		*/
3031		static class ConcurrentSkipListSubMap<K,V> extends AbstractMap<K,V>
3032		implements ConcurrentNavigableMap<K,V>, java.io.Serializable {
#	Line 3048 | Line 3048 | public class ConcurrentSkipListMap<K,V>
3048
3049		/**
3050		* Creates a new submap.
3051	<	* @param least inclusive least value, or <tt>null</tt> if from start
3052	<	* @param fence exclusive upper bound or <tt>null</tt> if to end
3051	>	* @param least inclusive least value, or {@code null} if from start
3052	>	* @param fence exclusive upper bound or {@code null} if to end
3053		* @throws IllegalArgumentException if least and fence non-null
3054		*  and least greater than fence
3055		*/
#	Line 3104 | Line 3104 | public class ConcurrentSkipListMap<K,V>
3104
3105		/**
3106		* Returns least key. Needed by ConcurrentSkipListSet.
3107	<	* @return least key or <tt>null</tt> if from start
3107	>	* @return least key or {@code null} if from start
3108		*/
3109		K getLeast() {
3110		return least;
#	Line 3112 | Line 3112 | public class ConcurrentSkipListMap<K,V>
3112
3113		/**
3114		* Returns fence key. Needed by ConcurrentSkipListSet.
3115	<	* @return fence key or <tt>null</tt> of to end
3115	>	* @return fence key or {@code null} of to end
3116		*/
3117		K getFence() {
3118		return fence;

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines