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.10 by jsr166, Wed Sep 1 20:12:39 2010 UTC vs.
Revision 1.20 by jsr166, Sat Dec 29 23:55:19 2012 UTC

#	Line 1 | Line 1
1		/*
2		* Written by Doug Lea with assistance from members of JCP JSR-166
3		* Expert Group and released to the public domain, as explained at
4	<	* http://creativecommons.org/licenses/publicdomain
4	>	* http://creativecommons.org/publicdomain/zero/1.0/
5		*/
6
7		package jsr166x;
#	Line 325 | Line 325 | public class ConcurrentSkipListMap<K,V>
325		private transient DescendingEntrySet descendingEntrySet;
326
327		/**
328	<	* Initialize or reset state. Needed by constructors, clone,
328	>	* Initializes or resets state. Needed by constructors, clone,
329		* clear, readObject. and ConcurrentSkipListSet.clone.
330		* (Note that comparator must be separately initialized.)
331		*/
#	Line 414 | Line 414 | public class ConcurrentSkipListMap<K,V>
414		}
415
416		/**
417	<	* Return true if this node is a marker. This method isn't
417	>	* Returns true if this node is a marker. This method isn't
418		* actually called in an any current code checking for markers
419		* because callers will have already read value field and need
420		* to use that read (not another done here) and so directly
#	Line 427 | Line 427 | public class ConcurrentSkipListMap<K,V>
427		}
428
429		/**
430	<	* Return true if this node is the header of base-level list.
430	>	* Returns true if this node is the header of base-level list.
431		* @return true if this node is header node
432		*/
433		boolean isBaseHeader() {
#	Line 465 | Line 465 | public class ConcurrentSkipListMap<K,V>
465		}
466
467		/**
468	<	* Return value if this node contains a valid key-value pair,
468	>	* Returns value if this node contains a valid key-value pair,
469		* else null.
470		* @return this node's value if it isn't a marker or header or
471		* is deleted, else null.
#	Line 478 | Line 478 | public class ConcurrentSkipListMap<K,V>
478		}
479
480		/**
481	<	* Create and return a new SnapshotEntry holding current
482	<	* mapping if this node holds a valid value, else null
481	>	* Creates and returns a new SnapshotEntry holding current
482	>	* mapping if this node holds a valid value, else null.
483		* @return new entry or null
484		*/
485		SnapshotEntry<K,V> createSnapshot() {
#	Line 599 | Line 599 | public class ConcurrentSkipListMap<K,V>
599		/**
600		* Returns the key corresponding to this entry.
601		*
602	<	* @return the key corresponding to this entry.
602	>	* @return the key corresponding to this entry
603		*/
604		public K getKey() {
605		return key;
#	Line 608 | Line 608 | public class ConcurrentSkipListMap<K,V>
608		/**
609		* Returns the value corresponding to this entry.
610		*
611	<	* @return the value corresponding to this entry.
611	>	* @return the value corresponding to this entry
612		*/
613		public V getValue() {
614		return value;
#	Line 616 | Line 616 | public class ConcurrentSkipListMap<K,V>
616
617		/**
618		* Always fails, throwing <tt>UnsupportedOperationException</tt>.
619	<	* @throws UnsupportedOperationException always.
619	>	* @throws UnsupportedOperationException always
620		*/
621		public V setValue(V value) {
622		throw new UnsupportedOperationException();
#	Line 646 | Line 646 | public class ConcurrentSkipListMap<K,V>
646		* Returns a String consisting of the key followed by an
647		* equals sign (<tt>"="</tt>) followed by the associated
648		* value.
649	<	* @return a String representation of this entry.
649	>	* @return a String representation of this entry
650		*/
651		public String toString() {
652		return getKey() + "=" + getValue();
#	Line 696 | Line 696 | public class ConcurrentSkipListMap<K,V>
696		}
697
698		/**
699	<	* Compare using comparator or natural ordering. Used when the
699	>	* Compares using comparator or natural ordering. Used when the
700		* ComparableUsingComparator approach doesn't apply.
701		*/
702		int compare(K k1, K k2) throws ClassCastException {
#	Line 708 | Line 708 | public class ConcurrentSkipListMap<K,V>
708		}
709
710		/**
711	<	* Return true if given key greater than or equal to least and
711	>	* Returns true if given key greater than or equal to least and
712		* strictly less than fence, bypassing either test if least or
713	<	* fence oare null. Needed mainly in submap operations.
713	>	* fence are null. Needed mainly in submap operations.
714		*/
715		boolean inHalfOpenRange(K key, K least, K fence) {
716		if (key == null)
#	Line 720 | Line 720 | public class ConcurrentSkipListMap<K,V>
720		}
721
722		/**
723	<	* Return true if given key greater than or equal to least and less
723	>	* Returns true if given key greater than or equal to least and less
724		* or equal to fence. Needed mainly in submap operations.
725		*/
726		boolean inOpenRange(K key, K least, K fence) {
#	Line 733 | Line 733 | public class ConcurrentSkipListMap<K,V>
733		/* ---------------- Traversal -------------- */
734
735		/**
736	<	* Return a base-level node with key strictly less than given key,
736	>	* Returns a base-level node with key strictly less than given key,
737		* or the base-level header if there is no such node.  Also
738		* unlinks indexes to deleted nodes found along the way.  Callers
739		* rely on this side-effect of clearing indices to deleted nodes.
#	Line 766 | Line 766 | public class ConcurrentSkipListMap<K,V>
766		}
767
768		/**
769	<	* Return node holding key or null if no such, clearing out any
769	>	* Returns node holding key or null if no such, clearing out any
770		* deleted nodes seen along the way.  Repeatedly traverses at
771		* base-level looking for key starting at predecessor returned
772		* from findPredecessor, processing base-level deletions as
#	Line 807 | Line 807 | public class ConcurrentSkipListMap<K,V>
807		* were performed.
808		*
809		* @param key the key
810	<	* @return node holding key, or null if no such.
810	>	* @return node holding key, or null if no such
811		*/
812		private Node<K,V> findNode(Comparable<K> key) {
813		for (;;) {
#	Line 865 | Line 865 | public class ConcurrentSkipListMap<K,V>
865		}
866		if (c == 0) {
867		Object v = r.node.value;
868	<	return (v != null)? (V)v : getUsingFindNode(key);
868	>	return (v != null) ? (V)v : getUsingFindNode(key);
869		}
870		bound = rk;
871		}
#	Line 878 | Line 878 | public class ConcurrentSkipListMap<K,V>
878		int c = key.compareTo(nk);
879		if (c == 0) {
880		Object v = n.value;
881	<	return (v != null)? (V)v : getUsingFindNode(key);
881	>	return (v != null) ? (V)v : getUsingFindNode(key);
882		}
883		if (c < 0)
884		return null;
#	Line 890 | Line 890 | public class ConcurrentSkipListMap<K,V>
890		}
891
892		/**
893	<	* Perform map.get via findNode.  Used as a backup if doGet
893	>	* Performs map.get via findNode.  Used as a backup if doGet
894		* encounters an in-progress deletion.
895		* @param key the key
896		* @return the value, or null if absent
#	Line 965 | Line 965 | public class ConcurrentSkipListMap<K,V>
965		}
966
967		/**
968	<	* Return a random level for inserting a new node.
968	>	* Returns a random level for inserting a new node.
969		* Hardwired to k=1, p=0.5, max 31.
970		*
971		* This uses a cheap pseudo-random function that according to
#	Line 987 | Line 987 | public class ConcurrentSkipListMap<K,V>
987		}
988
989		/**
990	<	* Create and add index nodes for given node.
990	>	* Creates and adds index nodes for given node.
991		* @param z the node
992		* @param level the level of the index
993		*/
#	Line 1039 | Line 1039 | public class ConcurrentSkipListMap<K,V>
1039		}
1040
1041		/**
1042	<	* Add given index nodes from given level down to 1.
1042	>	* Adds given index nodes from given level down to 1.
1043		* @param idx the topmost index node being inserted
1044		* @param h the value of head to use to insert. This must be
1045		* snapshotted by callers to provide correct insertion level
#	Line 1221 | Line 1221 | public class ConcurrentSkipListMap<K,V>
1221		}
1222
1223		/**
1224	<	* Remove first entry; return either its key or a snapshot.
1224	>	* Removes first entry; return either its key or a snapshot.
1225		* @param keyOnly if true return key, else return SnapshotEntry
1226		* (This is a little ugly, but avoids code duplication.)
1227		* @return null if empty, first key if keyOnly true, else key,value entry
#	Line 1246 | Line 1246 | public class ConcurrentSkipListMap<K,V>
1246		findFirst(); // retry
1247		clearIndexToFirst();
1248		K key = n.key;
1249	<	return (keyOnly)? key : new SnapshotEntry<K,V>(key, (V)v);
1249	>	return keyOnly ? key : new SnapshotEntry<K,V>(key, (V)v);
1250		}
1251		}
1252
1253		/**
1254	<	* Clear out index nodes associated with deleted first entry.
1255	<	* Needed by doRemoveFirst
1254	>	* Clears out index nodes associated with deleted first entry.
1255	>	* Needed by doRemoveFirst.
1256		*/
1257		private void clearIndexToFirst() {
1258		for (;;) {
#	Line 1271 | Line 1271 | public class ConcurrentSkipListMap<K,V>
1271		}
1272
1273		/**
1274	<	* Remove first entry; return key or null if empty.
1274	>	* Removes first entry; return key or null if empty.
1275		*/
1276		K pollFirstKey() {
1277		return (K)doRemoveFirst(true);
#	Line 1306 | Line 1306 | public class ConcurrentSkipListMap<K,V>
1306		Node<K,V> n = b.next;
1307		for (;;) {
1308		if (n == null)
1309	<	return (b.isBaseHeader())? null : b;
1309	>	return b.isBaseHeader() ? null : b;
1310		Node<K,V> f = n.next;            // inconsistent read
1311		if (n != b.next)
1312		break;
#	Line 1368 | Line 1368 | public class ConcurrentSkipListMap<K,V>
1368		if (head.right == null)
1369		tryReduceLevel();
1370		}
1371	<	return (keyOnly)? key : new SnapshotEntry<K,V>(key, (V)v);
1371	>	return keyOnly ? key : new SnapshotEntry<K,V>(key, (V)v);
1372		}
1373		}
1374		}
#	Line 1378 | Line 1378 | public class ConcurrentSkipListMap<K,V>
1378		* last valid node. Needed by doRemoveLast. It is possible that
1379		* all successors of returned node will have been deleted upon
1380		* return, in which case this method can be retried.
1381	<	* @return likely predecessor of last node.
1381	>	* @return likely predecessor of last node
1382		*/
1383		private Node<K,V> findPredecessorOfLast() {
1384		for (;;) {
#	Line 1405 | Line 1405 | public class ConcurrentSkipListMap<K,V>
1405		}
1406
1407		/**
1408	<	* Remove last entry; return key or null if empty.
1408	>	* Removes last entry; return key or null if empty.
1409		*/
1410		K pollLastKey() {
1411		return (K)doRemoveLast(true);
#	Line 1432 | Line 1432 | public class ConcurrentSkipListMap<K,V>
1432		Node<K,V> n = b.next;
1433		for (;;) {
1434		if (n == null)
1435	<	return ((rel & LT) == 0 || b.isBaseHeader())? null : b;
1435	>	return ((rel & LT) == 0 || b.isBaseHeader()) ? null : b;
1436		Node<K,V> f = n.next;
1437		if (n != b.next)                  // inconsistent read
1438		break;
#	Line 1448 | Line 1448 | public class ConcurrentSkipListMap<K,V>
1448		(c <  0 && (rel & LT) == 0))
1449		return n;
1450		if ( c <= 0 && (rel & LT) != 0)
1451	<	return (b.isBaseHeader())? null : b;
1451	>	return b.isBaseHeader() ? null : b;
1452		b = n;
1453		n = f;
1454		}
#	Line 1456 | Line 1456 | public class ConcurrentSkipListMap<K,V>
1456		}
1457
1458		/**
1459	<	* Return SnapshotEntry for results of findNear.
1459	>	* Returns SnapshotEntry for results of findNear.
1460		* @param kkey the key
1461		* @param rel the relation -- OR'ed combination of EQ, LT, GT
1462		* @return Entry fitting relation, or null if no such
#	Line 1473 | Line 1473 | public class ConcurrentSkipListMap<K,V>
1473		}
1474
1475		/**
1476	<	* Return ceiling, or first node if key is <tt>null</tt>
1476	>	* Returns ceiling, or first node if key is <tt>null</tt>.
1477		*/
1478		Node<K,V> findCeiling(K key) {
1479	<	return (key == null)? findFirst() : findNear(key, GT|EQ);
1479	>	return (key == null) ? findFirst() : findNear(key, GT|EQ);
1480		}
1481
1482		/**
1483	<	* Return lower node, or last node if key is <tt>null</tt>
1483	>	* Returns lower node, or last node if key is <tt>null</tt>.
1484		*/
1485		Node<K,V> findLower(K key) {
1486	<	return (key == null)? findLast() : findNear(key, LT);
1486	>	return (key == null) ? findLast() : findNear(key, LT);
1487		}
1488
1489		/**
1490	<	* Return SnapshotEntry or key for results of findNear ofter screening
1490	>	* Returns SnapshotEntry or key for results of findNear ofter screening
1491		* to ensure result is in given range. Needed by submaps.
1492		* @param kkey the key
1493		* @param rel the relation -- OR'ed combination of EQ, LT, GT
#	Line 1513 | Line 1513 | public class ConcurrentSkipListMap<K,V>
1513		K k = n.key;
1514		V v = n.getValidValue();
1515		if (v != null)
1516	<	return keyOnly? k : new SnapshotEntry<K,V>(k, v);
1516	>	return keyOnly ? k : new SnapshotEntry<K,V>(k, v);
1517		}
1518		}
1519
1520		/**
1521	<	* Find and remove least element of subrange.
1521	>	* Finds and removes least element of subrange.
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
#	Line 1534 | Line 1534 | public class ConcurrentSkipListMap<K,V>
1534		return null;
1535		V v = doRemove(k, null);
1536		if (v != null)
1537	<	return (keyOnly)? k : new SnapshotEntry<K,V>(k, v);
1537	>	return keyOnly ? k : new SnapshotEntry<K,V>(k, v);
1538		}
1539		}
1540
1541		/**
1542	<	* Find and remove greatest element of subrange.
1542	>	* Finds and removes greatest element of subrange.
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
#	Line 1555 | Line 1555 | public class ConcurrentSkipListMap<K,V>
1555		return null;
1556		V v = doRemove(k, null);
1557		if (v != null)
1558	<	return (keyOnly)? k : new SnapshotEntry<K,V>(k, v);
1558	>	return keyOnly ? k : new SnapshotEntry<K,V>(k, v);
1559		}
1560		}
1561
#	Line 1586 | Line 1586 | public class ConcurrentSkipListMap<K,V>
1586		* Constructs a new map containing the same mappings as the given map,
1587		* sorted according to the keys' <i>natural order</i>.
1588		*
1589	<	* @param  m the map whose mappings are to be placed in this map.
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>.
1591	>	*         are not mutually comparable
1592	>	* @throws NullPointerException if the specified map is <tt>null</tt>
1593		*/
1594		public ConcurrentSkipListMap(Map<? extends K, ? extends V> m) {
1595		this.comparator = null;
#	Line 1615 | Line 1615 | public class ConcurrentSkipListMap<K,V>
1615		* Returns a shallow copy of this <tt>Map</tt> instance. (The keys and
1616		* values themselves are not cloned.)
1617		*
1618	<	* @return a shallow copy of this Map.
1618	>	* @return a shallow copy of this Map
1619		*/
1620		public Object clone() {
1621		ConcurrentSkipListMap<K,V> clone = null;
#	Line 1689 | Line 1689 | public class ConcurrentSkipListMap<K,V>
1689		/* ---------------- Serialization -------------- */
1690
1691		/**
1692	<	* Save the state of the <tt>Map</tt> instance to a stream.
1692	>	* Saves the state of the <tt>Map</tt> 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
#	Line 1714 | Line 1714 | public class ConcurrentSkipListMap<K,V>
1714		}
1715
1716		/**
1717	<	* Reconstitute the <tt>Map</tt> instance from a stream.
1717	>	* Reconstitutes the <tt>Map</tt> instance from a stream.
1718		*/
1719		private void readObject(final java.io.ObjectInputStream s)
1720		throws java.io.IOException, ClassNotFoundException {
#	Line 1779 | Line 1779 | public class ConcurrentSkipListMap<K,V>
1779		/**
1780		* Returns <tt>true</tt> if this map contains a mapping for the specified
1781		* key.
1782	<	* @param key key whose presence in this map is to be tested.
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
1784	<	*            specified key.
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>.
1786	>	*                  currently in the map
1787	>	* @throws NullPointerException if the key is <tt>null</tt>
1788		*/
1789		public boolean containsKey(Object key) {
1790		return doGet(key) != null;
#	Line 1794 | Line 1794 | public class ConcurrentSkipListMap<K,V>
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.
1796		*
1797	<	* @param key key whose associated value is to be returned.
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	>	*               <tt>null</tt> 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>.
1801	>	*                  currently in the map
1802	>	* @throws NullPointerException if the key is <tt>null</tt>
1803		*/
1804		public V get(Object key) {
1805		return doGet(key);
#	Line 1810 | Line 1810 | public class ConcurrentSkipListMap<K,V>
1810		* If the map previously contained a mapping for this key, the old
1811		* value is replaced.
1812		*
1813	<	* @param key key with which the specified value is to be associated.
1814	<	* @param value value to be associated with the specified key.
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>
1817	<	*         if there was no mapping for key.
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>.
1819	>	*            currently in the map
1820	>	* @throws NullPointerException if the key or value are <tt>null</tt>
1821		*/
1822		public V put(K key, V value) {
1823		if (value == null)
#	Line 1830 | Line 1830 | public class ConcurrentSkipListMap<K,V>
1830		*
1831		* @param  key key for which mapping should be removed
1832		* @return previous value associated with specified key, or <tt>null</tt>
1833	<	*         if there was no mapping for key.
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>.
1836	>	*            currently in the map
1837	>	* @throws NullPointerException if the key is <tt>null</tt>
1838		*/
1839		public V remove(Object key) {
1840		return doRemove(key, null);
#	Line 1845 | Line 1845 | public class ConcurrentSkipListMap<K,V>
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.
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>.
1850	>	*          <tt>false</tt> otherwise
1851	>	* @throws  NullPointerException  if the value is <tt>null</tt>
1852		*/
1853		public boolean containsValue(Object value) {
1854		if (value == null)
#	Line 1875 | Line 1875 | public class ConcurrentSkipListMap<K,V>
1875		* will be inaccurate. Thus, this method is typically not very
1876		* useful in concurrent applications.
1877		*
1878	<	* @return  the number of elements in this map.
1878	>	* @return  the number of elements in this map
1879		*/
1880		public int size() {
1881		long count = 0;
#	Line 1883 | Line 1883 | public class ConcurrentSkipListMap<K,V>
1883		if (n.getValidValue() != null)
1884		++count;
1885		}
1886	<	return (count >= Integer.MAX_VALUE)? Integer.MAX_VALUE : (int)count;
1886	>	return (count >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)count;
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.
1891	>	* @return <tt>true</tt> if this map contains no key-value mappings
1892		*/
1893		public boolean isEmpty() {
1894		return findFirst() == null;
#	Line 1915 | Line 1915 | public class ConcurrentSkipListMap<K,V>
1915		* construction of the iterator, and may (but is not guaranteed to)
1916		* reflect any modifications subsequent to construction.
1917		*
1918	<	* @return a set view of the keys contained in this map.
1918	>	* @return a set view of the keys contained in this map
1919		*/
1920		public Set<K> keySet() {
1921		/*
#	Line 1946 | Line 1946 | public class ConcurrentSkipListMap<K,V>
1946		* construction of the iterator, and may (but is not guaranteed
1947		* to) reflect any modifications subsequent to construction.
1948		*
1949	<	* @return a set view of the keys contained in this map.
1949	>	* @return a set view of the keys contained in this map
1950		*/
1951		public Set<K> descendingKeySet() {
1952		/*
#	Line 1978 | Line 1978 | public class ConcurrentSkipListMap<K,V>
1978		* iterator, and may (but is not guaranteed to) reflect any
1979		* modifications subsequent to construction.
1980		*
1981	<	* @return a collection view of the values contained in this map.
1981	>	* @return a collection view of the values contained in this map
1982		*/
1983		public Collection<V> values() {
1984		Values vs = values;
#	Line 2005 | Line 2005 | public class ConcurrentSkipListMap<K,V>
2005		* <tt>iterator.next()</tt> do <em>not</em> support the
2006		* <tt>setValue</tt> operation.
2007		*
2008	<	* @return a collection view of the mappings contained in this map.
2008	>	* @return a collection view of the mappings contained in this map
2009		*/
2010		public Set<Map.Entry<K,V>> entrySet() {
2011		EntrySet es = entrySet;
#	Line 2032 | Line 2032 | public class ConcurrentSkipListMap<K,V>
2032		* <tt>iterator.next()</tt> do <em>not</em> support the
2033		* <tt>setValue</tt> operation.
2034		*
2035	<	* @return a collection view of the mappings contained in this map.
2035	>	* @return a collection view of the mappings contained in this map
2036		*/
2037		public Set<Map.Entry<K,V>> descendingEntrySet() {
2038		DescendingEntrySet es = descendingEntrySet;
#	Line 2052 | Line 2052 | public class ConcurrentSkipListMap<K,V>
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.
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
2057		*/
2058		public boolean equals(Object o) {
2059		if (o == this)
#	Line 2094 | Line 2094 | public class ConcurrentSkipListMap<K,V>
2094		* This is equivalent to
2095		* <pre>
2096		*   if (!map.containsKey(key))
2097	<	*      return map.put(key, value);
2097	>	*     return map.put(key, value);
2098		*   else
2099	<	*      return map.get(key);
2099	>	*     return map.get(key);
2100		* </pre>
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.
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>
2105	<	*         if there was no mapping for key.
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>.
2108	>	*            currently in the map
2109	>	* @throws NullPointerException if the key or value are <tt>null</tt>
2110		*/
2111		public V putIfAbsent(K key, V value) {
2112		if (value == null)
#	Line 2115 | Line 2115 | public class ConcurrentSkipListMap<K,V>
2115		}
2116
2117		/**
2118	<	* Remove entry for key only if currently mapped to given value.
2118	>	* Removes entry for key only if currently mapped to given value.
2119		* Acts as
2120		* <pre>
2121		*  if ((map.containsKey(key) && map.get(key).equals(value)) {
#	Line 2124 | Line 2124 | public class ConcurrentSkipListMap<K,V>
2124		* } else return false;
2125		* </pre>
2126		* except that the action is performed atomically.
2127	<	* @param key key with which the specified value is associated.
2128	<	* @param value value associated with the specified key.
2127	>	* @param key key with which the specified value is associated
2128	>	* @param value value associated with the specified key
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>.
2131	>	*            currently in the map
2132	>	* @throws NullPointerException if the key or value are <tt>null</tt>
2133		*/
2134		public boolean remove(Object key, Object value) {
2135		if (value == null)
#	Line 2147 | Line 2147 | public class ConcurrentSkipListMap<K,V>
2147		* } else return false;
2148		* </pre>
2149		* except that the action is performed atomically.
2150	<	* @param key key with which the specified value is associated.
2151	<	* @param oldValue value expected to be associated with the specified key.
2152	<	* @param newValue value to be associated with the specified key.
2150	>	* @param key key with which the specified value is associated
2151	>	* @param oldValue value expected to be associated with the specified key
2152	>	* @param newValue value to be associated with the specified key
2153		* @return true if the value was replaced
2154		* @throws ClassCastException if the key cannot be compared with the keys
2155	<	*            currently in the map.
2155	>	*            currently in the map
2156		* @throws NullPointerException if key, oldValue or newValue are
2157	<	* <tt>null</tt>.
2157	>	* <tt>null</tt>
2158		*/
2159		public boolean replace(K key, V oldValue, V newValue) {
2160		if (oldValue == null || newValue == null)
#	Line 2183 | Line 2183 | public class ConcurrentSkipListMap<K,V>
2183		* } else return null;
2184		* </pre>
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.
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>
2189	<	*         if there was no mapping for key.
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>.
2191	>	*            currently in the map
2192	>	* @throws NullPointerException if the key or value are <tt>null</tt>
2193		*/
2194		public V replace(K key, V value) {
2195		if (value == null)
#	Line 2221 | Line 2221 | public class ConcurrentSkipListMap<K,V>
2221		/**
2222		* Returns the first (lowest) key currently in this map.
2223		*
2224	<	* @return the first (lowest) key currently in this map.
2225	<	* @throws    NoSuchElementException Map is empty.
2224	>	* @return the first (lowest) key currently in this map
2225	>	* @throws    NoSuchElementException Map is empty
2226		*/
2227		public K firstKey() {
2228		Node<K,V> n = findFirst();
#	Line 2234 | Line 2234 | public class ConcurrentSkipListMap<K,V>
2234		/**
2235		* Returns the last (highest) key currently in this map.
2236		*
2237	<	* @return the last (highest) key currently in this map.
2238	<	* @throws    NoSuchElementException Map is empty.
2237	>	* @return the last (highest) key currently in this map
2238	>	* @throws    NoSuchElementException Map is empty
2239		*/
2240		public K lastKey() {
2241		Node<K,V> n = findLast();
#	Line 2250 | Line 2250 | public class ConcurrentSkipListMap<K,V>
2250		* <tt>fromKey</tt> and <tt>toKey</tt> 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	<
2254	<	* @param fromKey low endpoint (inclusive) of the subMap.
2255	<	* @param toKey high endpoint (exclusive) of the subMap.
2253	>	*
2254	>	* @param fromKey low endpoint (inclusive) of the subMap
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	>	* <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive
2259		*
2260		* @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt>
2261		*         cannot be compared to one another using this map's comparator
2262	<	*         (or, if the map has no comparator, using natural ordering).
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>.
2264	>	*         <tt>toKey</tt>
2265		* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
2266	<	*               <tt>null</tt>.
2266	>	*               <tt>null</tt>
2267		*/
2268		public ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey) {
2269		if (fromKey == null || toKey == null)
#	Line 2276 | Line 2276 | public class ConcurrentSkipListMap<K,V>
2276		* strictly less than <tt>toKey</tt>.  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.
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 <tt>toKey</tt>
2282		*
2283		* @throws ClassCastException if <tt>toKey</tt> 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 <tt>toKey</tt> does not implement <tt>Comparable</tt>)
2286	>	* @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt>
2287		*/
2288		public ConcurrentNavigableMap<K,V> headMap(K toKey) {
2289		if (toKey == null)
#	Line 2296 | Line 2296 | public class ConcurrentSkipListMap<K,V>
2296		* greater than or equal to <tt>fromKey</tt>.  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.
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>.
2301	>	* greater than or equal to <tt>fromKey</tt>
2302		* @throws ClassCastException if <tt>fromKey</tt> 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>.
2305	>	* <tt>Comparable</tt>)
2306	>	* @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt>
2307		*/
2308	<	public ConcurrentNavigableMap<K,V>  tailMap(K fromKey) {
2308	>	public ConcurrentNavigableMap<K,V> tailMap(K fromKey) {
2309		if (fromKey == null)
2310		throw new NullPointerException();
2311		return new ConcurrentSkipListSubMap(this, fromKey, null);
#	Line 2319 | Line 2319 | public class ConcurrentSkipListMap<K,V>
2319		* there is no such entry. The returned entry does <em>not</em>
2320		* support the <tt>Entry.setValue</tt> method.
2321		*
2322	<	* @param key the key.
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	>	* <tt>null</tt> 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>.
2326	>	* keys currently in the map
2327	>	* @throws NullPointerException if key is <tt>null</tt>
2328		*/
2329		public Map.Entry<K,V> ceilingEntry(K key) {
2330		return getNear(key, GT|EQ);
#	Line 2334 | Line 2334 | public class ConcurrentSkipListMap<K,V>
2334		* Returns least key greater than or equal to the given key, or
2335		* <tt>null</tt> if there is no such key.
2336		*
2337	<	* @param key the key.
2337	>	* @param key the key
2338		* @return the ceiling key, or <tt>null</tt>
2339	<	* if there is no such key.
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>.
2341	>	*            currently in the map
2342	>	* @throws NullPointerException if key is <tt>null</tt>
2343		*/
2344		public K ceilingKey(K key) {
2345		Node<K,V> n = findNear(key, GT|EQ);
2346	<	return (n == null)? null : n.key;
2346	>	return (n == null) ? null : n.key;
2347		}
2348
2349		/**
#	Line 2352 | Line 2352 | public class ConcurrentSkipListMap<K,V>
2352		* such entry. The returned entry does <em>not</em> support
2353		* the <tt>Entry.setValue</tt> method.
2354		*
2355	<	* @param key the key.
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 <tt>null</tt> 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>.
2359	>	*            currently in the map
2360	>	* @throws NullPointerException if key is <tt>null</tt>
2361		*/
2362		public Map.Entry<K,V> lowerEntry(K key) {
2363		return getNear(key, LT);
#	Line 2367 | Line 2367 | public class ConcurrentSkipListMap<K,V>
2367		* Returns the greatest key strictly less than the given key, or
2368		* <tt>null</tt> if there is no such key.
2369		*
2370	<	* @param key the key.
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 <tt>null</tt> 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>.
2374	>	*            currently in the map
2375	>	* @throws NullPointerException if key is <tt>null</tt>
2376		*/
2377		public K lowerKey(K key) {
2378		Node<K,V> n = findNear(key, LT);
2379	<	return (n == null)? null : n.key;
2379	>	return (n == null) ? null : n.key;
2380		}
2381
2382		/**
#	Line 2385 | Line 2385 | public class ConcurrentSkipListMap<K,V>
2385		* is no such entry. The returned entry does <em>not</em> support
2386		* the <tt>Entry.setValue</tt> method.
2387		*
2388	<	* @param key the key.
2388	>	* @param key the key
2389		* @return an Entry associated with floor of given key, or <tt>null</tt>
2390	<	* if there is no such Entry.
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>.
2392	>	*            currently in the map
2393	>	* @throws NullPointerException if key is <tt>null</tt>
2394		*/
2395		public Map.Entry<K,V> floorEntry(K key) {
2396		return getNear(key, LT|EQ);
#	Line 2401 | Line 2401 | public class ConcurrentSkipListMap<K,V>
2401		* less than or equal to the given key, or <tt>null</tt> if there
2402		* is no such key.
2403		*
2404	<	* @param key the key.
2404	>	* @param key the key
2405		* @return the floor of given key, or <tt>null</tt> if there is no
2406	<	* such key.
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>.
2408	>	*            currently in the map
2409	>	* @throws NullPointerException if key is <tt>null</tt>
2410		*/
2411		public K floorKey(K key) {
2412		Node<K,V> n = findNear(key, LT|EQ);
2413	<	return (n == null)? null : n.key;
2413	>	return (n == null) ? null : n.key;
2414		}
2415
2416		/**
#	Line 2419 | Line 2419 | public class ConcurrentSkipListMap<K,V>
2419		* is no such entry. The returned entry does <em>not</em> support
2420		* the <tt>Entry.setValue</tt> method.
2421		*
2422	<	* @param key the key.
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	>	* <tt>null</tt> 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>.
2426	>	*            currently in the map
2427	>	* @throws NullPointerException if key is <tt>null</tt>
2428		*/
2429		public Map.Entry<K,V> higherEntry(K key) {
2430		return getNear(key, GT);
#	Line 2434 | Line 2434 | public class ConcurrentSkipListMap<K,V>
2434		* Returns the least key strictly greater than the given key, or
2435		* <tt>null</tt> if there is no such key.
2436		*
2437	<	* @param key the key.
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	>	* <tt>null</tt> 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>.
2441	>	*            currently in the map
2442	>	* @throws NullPointerException if key is <tt>null</tt>
2443		*/
2444		public K higherKey(K key) {
2445		Node<K,V> n = findNear(key, GT);
2446	<	return (n == null)? null : n.key;
2446	>	return (n == null) ? null : n.key;
2447		}
2448
2449		/**
#	Line 2453 | Line 2453 | public class ConcurrentSkipListMap<K,V>
2453		* the <tt>Entry.setValue</tt> method.
2454		*
2455		* @return an Entry with least key, or <tt>null</tt>
2456	<	* if the map is empty.
2456	>	* if the map is empty
2457		*/
2458		public Map.Entry<K,V> firstEntry() {
2459		for (;;) {
#	Line 2473 | Line 2473 | public class ConcurrentSkipListMap<K,V>
2473		* the <tt>Entry.setValue</tt> method.
2474		*
2475		* @return an Entry with greatest key, or <tt>null</tt>
2476	<	* if the map is empty.
2476	>	* if the map is empty
2477		*/
2478		public Map.Entry<K,V> lastEntry() {
2479		for (;;) {
#	Line 2493 | Line 2493 | public class ConcurrentSkipListMap<K,V>
2493		* the <tt>Entry.setValue</tt> method.
2494		*
2495		* @return the removed first entry of this map, or <tt>null</tt>
2496	<	* if the map is empty.
2496	>	* if the map is empty
2497		*/
2498		public Map.Entry<K,V> pollFirstEntry() {
2499		return (SnapshotEntry<K,V>)doRemoveFirst(false);
#	Line 2506 | Line 2506 | public class ConcurrentSkipListMap<K,V>
2506		* the <tt>Entry.setValue</tt> method.
2507		*
2508		* @return the removed last entry of this map, or <tt>null</tt>
2509	<	* if the map is empty.
2509	>	* if the map is empty
2510		*/
2511		public Map.Entry<K,V> pollLastEntry() {
2512		return (SnapshotEntry<K,V>)doRemoveLast(false);
#	Line 3050 | Line 3050 | public class ConcurrentSkipListMap<K,V>
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
3053	<	* @throws IllegalArgumentException if least and fence nonnull
3053	>	* @throws IllegalArgumentException if least and fence non-null
3054		*  and least greater than fence
3055		*/
3056		ConcurrentSkipListSubMap(ConcurrentSkipListMap<K,V> map,
#	Line 3128 | Line 3128 | public class ConcurrentSkipListMap<K,V>
3128
3129		public V get(Object key) {
3130		K k = (K)key;
3131	<	return ((!inHalfOpenRange(k)) ? null : m.get(k));
3131	>	return (!inHalfOpenRange(k)) ? null : m.get(k);
3132		}
3133
3134		public V put(K key, V value) {
#	Line 3138 | Line 3138 | public class ConcurrentSkipListMap<K,V>
3138
3139		public V remove(Object key) {
3140		K k = (K)key;
3141	<	return (!inHalfOpenRange(k))? null : m.remove(k);
3141	>	return (!inHalfOpenRange(k)) ? null : m.remove(k);
3142		}
3143
3144		public int size() {
#	Line 3149 | Line 3149 | public class ConcurrentSkipListMap<K,V>
3149		if (n.getValidValue() != null)
3150		++count;
3151		}
3152	<	return count >= Integer.MAX_VALUE? Integer.MAX_VALUE : (int)count;
3152	>	return (count >= Integer.MAX_VALUE) ?
3153	>	Integer.MAX_VALUE : (int)count;
3154		}
3155
3156		public boolean isEmpty() {
#	Line 3240 | Line 3241 | public class ConcurrentSkipListMap<K,V>
3241		return new ConcurrentSkipListSubMap(m, least, toKey);
3242		}
3243
3244	<	public  ConcurrentNavigableMap<K,V> tailMap(K fromKey) {
3244	>	public ConcurrentNavigableMap<K,V> tailMap(K fromKey) {
3245		if (fromKey == null)
3246		throw new NullPointerException();
3247		if (!inOpenRange(fromKey))

Diff Legend

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