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.1 by dl, Wed Aug 11 10:58:15 2004 UTC vs.
Revision 1.2 by dl, Mon Sep 6 17:01:54 2004 UTC

#	Line 11 | Line 11 | import java.util.concurrent.*;
11		import java.util.concurrent.atomic.*;
12
13		/**
14	<	* A scalable {@link SortedMap} and {@link ConcurrentMap}
15	<	* implementation.  This class maintains a map in ascending key order,
16	<	* sorted according to the <i>natural order</i> for the key's class
17	<	* (see {@link Comparable}), or by the {@link Comparator} provided at
18	<	* creation time, depending on which constructor is used.
14	>	* A scalable {@link ConcurrentNavigableMap} implementation.  This
15	>	* class maintains a map in ascending key order, sorted according to
16	>	* the <i>natural order</i> for the key's class (see {@link
17	>	* Comparable}), or by the {@link Comparator} provided at creation
18	>	* time, depending on which constructor is used.
19		*
20		* <p>This class implements a concurrent variant of <a
21		* href="http://www.cs.umd.edu/~pugh/">SkipLists</a> providing
#	Line 29 | Line 29 | import java.util.concurrent.atomic.*;
29		* ConcurrentModificationException}, and may proceed concurrently with
30		* other operations.
31		*
32	–	* <p>This class provides extended <tt>SortedMap</tt> methods
33	–	* returning <tt>Map.Entry</tt> key-value pairs that may be useful in
34	–	* searching for closest matches. Methods <tt>lowerEntry</tt>,
35	–	* <tt>floorEntry</tt>, <tt>ceilingEntry</tt>, and
36	–	* <tt>higherEntry</tt> return entries associated with keys
37	–	* respectively less, less than or equal, greater than or equal, and
38	–	* greater than a given key, returning null if there is no such key.
39	–	* These methods are designed for locating, not traversing entries. To
40	–	* traverse, use view iterators and/or <tt>submap</tt>. The class
41	–	* additionally supports method <tt>removeFirstEntry</tt> that
42	–	* atomically returns and removes the first mapping (i.e., with least
43	–	* key), if one exists.
44	–	*
32		* <p> All <tt>Map.Entry</tt> pairs returned by methods in this class
33		* and its views represent snapshots of mappings at the time they were
34		* produced. They do <em>not</em> support the <tt>Entry.setValue</tt>
#	Line 49 | Line 36 | import java.util.concurrent.atomic.*;
36		* associated map using <tt>put</tt>, <tt>putIfAbsent</tt>, or
37		* <tt>replace</tt>, depending on exactly which effect you need.)
38		*
52	–	* <p>The {@link ConcurrentSkipListSubMap} objects returned by methods
53	–	* <tt>submap</tt>, <tt>headMap</tt>, and <tt>tailMap</tt> support the
54	–	* same extended set of operations as this class, but operate on their
55	–	* designated subrange of mappings.
56	–	*
39		* <p>Beware that, unlike in most collections, the <tt>size</tt>
40		* method is <em>not</em> a constant-time operation. Because of the
41		* asynchronous nature of these maps, determining the current number
#	Line 71 | Line 53 | import java.util.concurrent.atomic.*;
53		* @param <V> the type of mapped values
54		*/
55		public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
56	<	implements ConcurrentMap<K,V>,
75	<	SortedMap<K,V>,
56	>	implements ConcurrentNavigableMap<K,V>,
57		Cloneable,
58		java.io.Serializable {
59		/*
#	Line 136 | Line 117 | public class ConcurrentSkipListMap<K,V>
117		* space by defining marker nodes not to have key/value fields, it
118		* isn't worth the extra type-testing overhead.  The deletion
119		* markers are rarely encountered during traversal and are
120	<	* normally quickly garbage collected.
120	>	* normally quickly garbage collected. (Note that this technique
121	>	* would not work well in systems without garbage collection.)
122		*
123		* In addition to using deletion markers, the lists also use
124		* nullness of value fields to indicate deletion, in a style
#	Line 276 | Line 258 | public class ConcurrentSkipListMap<K,V>
258		*
259		* For explanation of algorithms sharing at least a couple of
260		* features with this one, see Mikhail Fomitchev's thesis
261	<	* (http://www.cs.yorku.ca/~mikhail/) and Keir Fraser's thesis
262	<	* (http://www.cl.cam.ac.uk/users/kaf24/).
261	>	* (http://www.cs.yorku.ca/~mikhail/), Keir Fraser's thesis
262	>	* (http://www.cl.cam.ac.uk/users/kaf24/), and papers by
263	>	* Håkan Sundell (http://www.cs.chalmers.se/~phs/).
264		*
265		* Given the use of tree-like index nodes, you might wonder why
266		* this doesn't use some kind of search tree instead, which would
#	Line 1349 | Line 1332 | public class ConcurrentSkipListMap<K,V>
1332		}
1333		}
1334
1335	+	/**
1336	+	* Temporary helper method for two-pass implementation of
1337	+	* removeLastEntry, mostly pasted from doRemove.
1338	+	* TODO: replace with one-pass implementation
1339	+	*/
1340	+	private Object removeIfLast(K kkey) {
1341	+	Comparable<K> key = comparable(kkey);
1342	+	for (;;) {
1343	+	Node<K,V> b = findPredecessor(key);
1344	+	Node<K,V> n = b.next;
1345	+	for (;;) {
1346	+	if (n == null)
1347	+	return null;
1348	+	Node<K,V> f = n.next;
1349	+	if (n != b.next)                    // inconsistent read
1350	+	break;
1351	+	Object v = n.value;
1352	+	if (v == null) {                    // n is deleted
1353	+	n.helpDelete(b, f);
1354	+	break;
1355	+	}
1356	+	if (v == n || b.value == null)      // b is deleted
1357	+	break;
1358	+	int c = key.compareTo(n.key);
1359	+	if (c < 0)
1360	+	return null;
1361	+	if (c > 0) {
1362	+	b = n;
1363	+	n = f;
1364	+	continue;
1365	+	}
1366	+	if (f != null)                       // fail if n not last
1367	+	return null;
1368	+	if (!n.casValue(v, null))
1369	+	return null;
1370	+	if (!n.appendMarker(f) || !b.casNext(n, f))
1371	+	findNode(key);                  // Retry via findNode
1372	+	else {
1373	+	findPredecessor(key);           // Clean index
1374	+	if (head.right == null)
1375	+	tryReduceLevel();
1376	+	}
1377	+	return v;
1378	+	}
1379	+	}
1380	+	}
1381	+
1382	+	/**
1383	+	* Remove last entry; return SnapshotEntry or null if empty.
1384	+	*/
1385	+	private SnapshotEntry<K,V> doRemoveLastEntry() {
1386	+	for (;;) {
1387	+	Node<K,V> l = findLast();
1388	+	if (l == null)
1389	+	return null;
1390	+	K k = l.key;
1391	+	Object v = removeIfLast(k);
1392	+	if (v != null)
1393	+	return new SnapshotEntry<K, V>(k, (V)v);
1394	+	}
1395	+	}
1396	+
1397	+	/**
1398	+	* Remove last entry; return key or null if empty.
1399	+	*/
1400	+	K removeLastKey() {
1401	+	for (;;) {
1402	+	Node<K,V> l = findLast();
1403	+	if (l == null)
1404	+	return null;
1405	+	K k = l.key;
1406	+	if (removeIfLast(k) != null)
1407	+	return k;
1408	+	}
1409	+	}
1410	+
1411		/* ---------------- Relational operations -------------- */
1412
1413		// Control values OR'ed as arguments to findNear
#	Line 2010 | Line 2069 | public class ConcurrentSkipListMap<K,V>
2069		* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
2070		*               <tt>null</tt>.
2071		*/
2072	<	public ConcurrentSkipListSubMap<K,V> subMap(K fromKey, K toKey) {
2072	>	public ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey) {
2073		if (fromKey == null || toKey == null)
2074		throw new NullPointerException();
2075		return new ConcurrentSkipListSubMap(this, fromKey, toKey);
#	Line 2030 | Line 2089 | public class ConcurrentSkipListMap<K,V>
2089		*         if <tt>toKey</tt> does not implement <tt>Comparable</tt>).
2090		* @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt>.
2091		*/
2092	<	public ConcurrentSkipListSubMap<K,V> headMap(K toKey) {
2092	>	public ConcurrentNavigableMap<K,V> headMap(K toKey) {
2093		if (toKey == null)
2094		throw new NullPointerException();
2095		return new ConcurrentSkipListSubMap(this, null, toKey);
#	Line 2049 | Line 2108 | public class ConcurrentSkipListMap<K,V>
2108		*         if <tt>fromKey</tt> does not implement <tt>Comparable</tt>).
2109		* @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt>.
2110		*/
2111	<	public ConcurrentSkipListSubMap<K,V>  tailMap(K fromKey) {
2111	>	public ConcurrentNavigableMap<K,V>  tailMap(K fromKey) {
2112		if (fromKey == null)
2113		throw new NullPointerException();
2114		return new ConcurrentSkipListSubMap(this, fromKey, null);
#	Line 2174 | Line 2233 | public class ConcurrentSkipListMap<K,V>
2233		* @return the removed first entry of this map, or null
2234		* if the map is empty.
2235		*/
2236	<	public Map.Entry<K,V> removeFirstEntry() {
2236	>	public Map.Entry<K,V> pollFirstEntry() {
2237		return doRemoveFirstEntry();
2238		}
2239
2240	+	/**
2241	+	* Removes and returns a key-value mapping associated with
2242	+	* the greatest key in this map, or null if the map is empty.
2243	+	* The returned entry does <em>not</em> support
2244	+	* the <tt>Entry.setValue</tt> method.
2245	+	*
2246	+	* @return the removed last entry of this map, or null
2247	+	* if the map is empty.
2248	+	*/
2249	+	public Map.Entry<K,V> pollLastEntry() {
2250	+	return doRemoveLastEntry();
2251	+	}
2252	+
2253		/* ---------------- Iterators -------------- */
2254
2255		/**
#	Line 2499 | Line 2571 | public class ConcurrentSkipListMap<K,V>
2571		}
2572		}
2573
2574	+
2575	+	/**
2576	+	* Find and remove greatest element of subrange.
2577	+	*/
2578	+	SnapshotEntry<K,V> removeLastEntryOfSubrange(K least, K fence) {
2579	+	for (;;) {
2580	+	Node<K,V> n = findLower(fence);
2581	+	if (n == null)
2582	+	return null;
2583	+	K k = n.key;
2584	+	if (least != null && compare(k, least) < 0)
2585	+	return null;
2586	+	V v = doRemove(k, null);
2587	+	if (v != null)
2588	+	return new SnapshotEntry<K,V>(k,v);
2589	+	}
2590	+	}
2591	+
2592	+
2593		SnapshotEntry<K,V> getCeiling(K key, K least, K fence) {
2594		return getNear(key, GT|EQ, least, fence);
2595		}
#	Line 2659 | Line 2750 | public class ConcurrentSkipListMap<K,V>
2750		return c.toArray(a);
2751		}
2752		}
2753	+
2754	+	/**
2755	+	* Submaps returned by {@link ConcurrentSkipListMap} submap operations
2756	+	* represent a subrange of mappings of their underlying
2757	+	* maps. Instances of this class support all methods of their
2758	+	* underlying maps, differing in that mappings outside their range are
2759	+	* ignored, and attempts to add mappings outside their ranges result
2760	+	* in {@link IllegalArgumentException}.  Instances of this class are
2761	+	* constructed only using the <tt>subMap</tt>, <tt>headMap</tt>, and
2762	+	* <tt>tailMap</tt> methods of their underlying maps.
2763	+	*/
2764	+	static class ConcurrentSkipListSubMap<K,V> extends AbstractMap<K,V>
2765	+	implements ConcurrentNavigableMap<K,V>, java.io.Serializable {
2766	+
2767	+	private static final long serialVersionUID = -7647078645895051609L;
2768	+
2769	+	/** Underlying map */
2770	+	private final ConcurrentSkipListMap<K,V> m;
2771	+	/** lower bound key, or null if from start */
2772	+	private final K least;
2773	+	/** upper fence key, or null if to end */
2774	+	private final K fence;
2775	+	// Lazily initialized view holders
2776	+	private transient Set<K> keySetView;
2777	+	private transient Set<Map.Entry<K,V>> entrySetView;
2778	+	private transient Collection<V> valuesView;
2779	+
2780	+	/**
2781	+	* Creates a new submap.
2782	+	* @param least inclusive least value, or null if from start
2783	+	* @param fence exclusive upper bound or null if to end
2784	+	* @throws IllegalArgumentException if least and fence nonnull
2785	+	*  and least greater than fence
2786	+	*/
2787	+	ConcurrentSkipListSubMap(ConcurrentSkipListMap<K,V> map,
2788	+	K least, K fence) {
2789	+	if (least != null && fence != null && map.compare(least, fence) > 0)
2790	+	throw new IllegalArgumentException("inconsistent range");
2791	+	this.m = map;
2792	+	this.least = least;
2793	+	this.fence = fence;
2794	+	}
2795	+
2796	+	/* ----------------  Utilities -------------- */
2797	+
2798	+	boolean inHalfOpenRange(K key) {
2799	+	return m.inHalfOpenRange(key, least, fence);
2800	+	}
2801	+
2802	+	boolean inOpenRange(K key) {
2803	+	return m.inOpenRange(key, least, fence);
2804	+	}
2805	+
2806	+	ConcurrentSkipListMap.Node<K,V> firstNode() {
2807	+	return m.findCeiling(least);
2808	+	}
2809	+
2810	+	ConcurrentSkipListMap.Node<K,V> lastNode() {
2811	+	return m.findLower(fence);
2812	+	}
2813	+
2814	+	boolean isBeforeEnd(ConcurrentSkipListMap.Node<K,V> n) {
2815	+	return (n != null &&
2816	+	(fence == null ||
2817	+	n.key == null || // pass by markers and headers
2818	+	m.compare(fence, n.key) > 0));
2819	+	}
2820	+
2821	+	void checkKey(K key) throws IllegalArgumentException {
2822	+	if (!inHalfOpenRange(key))
2823	+	throw new IllegalArgumentException("key out of range");
2824	+	}
2825	+
2826	+	/**
2827	+	* Returns underlying map. Needed by ConcurrentSkipListSet
2828	+	* @return the backing map
2829	+	*/
2830	+	ConcurrentSkipListMap<K,V> getMap() {
2831	+	return m;
2832	+	}
2833	+
2834	+	/**
2835	+	* Returns least key. Needed by ConcurrentSkipListSet
2836	+	* @return least key or null if from start
2837	+	*/
2838	+	K getLeast() {
2839	+	return least;
2840	+	}
2841	+
2842	+	/**
2843	+	* Returns fence key. Needed by ConcurrentSkipListSet
2844	+	* @return fence key or null of to end
2845	+	*/
2846	+	K getFence() {
2847	+	return fence;
2848	+	}
2849	+
2850	+	/**
2851	+	* Non-exception throwing version of firstKey needed by
2852	+	* ConcurrentSkipListSubSet
2853	+	* @return first key, or null if empty
2854	+	*/
2855	+	K lowestKey() {
2856	+	ConcurrentSkipListMap.Node<K,V> n = firstNode();
2857	+	if (isBeforeEnd(n))
2858	+	return n.key;
2859	+	else
2860	+	return null;
2861	+	}
2862	+
2863	+	/**
2864	+	* Non-exception throwing version of highestKey needed by
2865	+	* ConcurrentSkipListSubSet
2866	+	* @return last key, or null if empty
2867	+	*/
2868	+	K highestKey() {
2869	+	ConcurrentSkipListMap.Node<K,V> n = lastNode();
2870	+	if (isBeforeEnd(n))
2871	+	return n.key;
2872	+	else
2873	+	return null;
2874	+	}
2875	+
2876	+	/* ----------------  Map API methods -------------- */
2877	+
2878	+	/**
2879	+	* Returns <tt>true</tt> if this map contains a mapping for
2880	+	* the specified key.
2881	+	* @param key key whose presence in this map is to be tested.
2882	+	* @return <tt>true</tt> if this map contains a mapping for
2883	+	* the specified key.
2884	+	* @throws ClassCastException if the key cannot be compared
2885	+	* with the keys currently in the map.
2886	+	* @throws NullPointerException if the key is <tt>null</tt>.
2887	+	*/
2888	+	public boolean containsKey(Object key) {
2889	+	K k = (K)key;
2890	+	return inHalfOpenRange(k) && m.containsKey(k);
2891	+	}
2892	+
2893	+	/**
2894	+	* Returns the value to which this map maps the specified key.
2895	+	* Returns <tt>null</tt> if the map contains no mapping for
2896	+	* this key.
2897	+	*
2898	+	* @param key key whose associated value is to be returned.
2899	+	* @return the value to which this map maps the specified key,
2900	+	* or <tt>null</tt> if the map contains no mapping for the
2901	+	* key.
2902	+	* @throws ClassCastException if the key cannot be compared
2903	+	* with the keys currently in the map.
2904	+	* @throws NullPointerException if the key is <tt>null</tt>.
2905	+	*/
2906	+	public V get(Object key) {
2907	+	K k = (K)key;
2908	+	return ((!inHalfOpenRange(k)) ? null : m.get(k));
2909	+	}
2910	+
2911	+	/**
2912	+	* Associates the specified value with the specified key in
2913	+	* this map.  If the map previously contained a mapping for
2914	+	* this key, the old value is replaced.
2915	+	*
2916	+	* @param key key with which the specified value is to be associated.
2917	+	* @param value value to be associated with the specified key.
2918	+	*
2919	+	* @return previous value associated with specified key, or
2920	+	* <tt>null</tt> if there was no mapping for key.
2921	+	* @throws ClassCastException if the key cannot be compared
2922	+	* with the keys currently in the map.
2923	+	* @throws IllegalArgumentException if key outside range of
2924	+	* this submap.
2925	+	* @throws NullPointerException if the key or value are <tt>null</tt>.
2926	+	*/
2927	+	public V put(K key, V value) {
2928	+	checkKey(key);
2929	+	return m.put(key, value);
2930	+	}
2931	+
2932	+	/**
2933	+	* Removes the mapping for this key from this Map if present.
2934	+	*
2935	+	* @param key key for which mapping should be removed
2936	+	* @return previous value associated with specified key, or
2937	+	* <tt>null</tt> if there was no mapping for key.
2938	+	*
2939	+	* @throws ClassCastException if the key cannot be compared
2940	+	* with the keys currently in the map.
2941	+	* @throws NullPointerException if the key is <tt>null</tt>.
2942	+	*/
2943	+	public V remove(Object key) {
2944	+	K k = (K)key;
2945	+	return (!inHalfOpenRange(k))? null : m.remove(k);
2946	+	}
2947	+
2948	+	/**
2949	+	* Returns the number of elements in this map.  If this map
2950	+	* contains more than <tt>Integer.MAX_VALUE</tt> elements, it
2951	+	* returns <tt>Integer.MAX_VALUE</tt>.
2952	+	*
2953	+	* <p>Beware that, unlike in most collections, this method is
2954	+	* <em>NOT</em> a constant-time operation. Because of the
2955	+	* asynchronous nature of these maps, determining the current
2956	+	* number of elements requires traversing them all to count them.
2957	+	* Additionally, it is possible for the size to change during
2958	+	* execution of this method, in which case the returned result
2959	+	* will be inaccurate. Thus, this method is typically not very
2960	+	* useful in concurrent applications.
2961	+	*
2962	+	* @return  the number of elements in this map.
2963	+	*/
2964	+	public int size() {
2965	+	long count = 0;
2966	+	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
2967	+	isBeforeEnd(n);
2968	+	n = n.next) {
2969	+	if (n.getValidValue() != null)
2970	+	++count;
2971	+	}
2972	+	return count >= Integer.MAX_VALUE? Integer.MAX_VALUE : (int)count;
2973	+	}
2974	+
2975	+	/**
2976	+	* Returns <tt>true</tt> if this map contains no key-value mappings.
2977	+	* @return <tt>true</tt> if this map contains no key-value mappings.
2978	+	*/
2979	+	public boolean isEmpty() {
2980	+	return !isBeforeEnd(firstNode());
2981	+	}
2982	+
2983	+	/**
2984	+	* Returns <tt>true</tt> if this map maps one or more keys to the
2985	+	* specified value.  This operation requires time linear in the
2986	+	* Map size.
2987	+	*
2988	+	* @param value value whose presence in this Map is to be tested.
2989	+	* @return  <tt>true</tt> if a mapping to <tt>value</tt> exists;
2990	+	*              <tt>false</tt> otherwise.
2991	+	* @throws  NullPointerException  if the value is <tt>null</tt>.
2992	+	*/
2993	+	public boolean containsValue(Object value) {
2994	+	if (value == null)
2995	+	throw new NullPointerException();
2996	+	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
2997	+	isBeforeEnd(n);
2998	+	n = n.next) {
2999	+	V v = n.getValidValue();
3000	+	if (v != null && value.equals(v))
3001	+	return true;
3002	+	}
3003	+	return false;
3004	+	}
3005	+
3006	+	/**
3007	+	* Removes all mappings from this map.
3008	+	*/
3009	+	public void clear() {
3010	+	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3011	+	isBeforeEnd(n);
3012	+	n = n.next) {
3013	+	if (n.getValidValue() != null)
3014	+	m.remove(n.key);
3015	+	}
3016	+	}
3017	+
3018	+	/* ----------------  ConcurrentMap API methods -------------- */
3019	+
3020	+	/**
3021	+	* If the specified key is not already associated
3022	+	* with a value, associate it with the given value.
3023	+	* This is equivalent to
3024	+	* <pre>
3025	+	*   if (!map.containsKey(key))
3026	+	*      return map.put(key, value);
3027	+	*   else
3028	+	*      return map.get(key);
3029	+	* </pre>
3030	+	* Except that the action is performed atomically.
3031	+	* @param key key with which the specified value is to be associated.
3032	+	* @param value value to be associated with the specified key.
3033	+	* @return previous value associated with specified key, or
3034	+	* <tt>null</tt> if there was no mapping for key.
3035	+	*
3036	+	* @throws ClassCastException if the key cannot be compared
3037	+	* with the keys currently in the map.
3038	+	* @throws IllegalArgumentException if key outside range of
3039	+	* this submap.
3040	+	* @throws NullPointerException if the key or value are <tt>null</tt>.
3041	+	*/
3042	+	public V putIfAbsent(K key, V value) {
3043	+	checkKey(key);
3044	+	return m.putIfAbsent(key, value);
3045	+	}
3046	+
3047	+	/**
3048	+	* Remove entry for key only if currently mapped to given value.
3049	+	* Acts as
3050	+	* <pre>
3051	+	*  if ((map.containsKey(key) && map.get(key).equals(value)) {
3052	+	*     map.remove(key);
3053	+	*     return true;
3054	+	* } else return false;
3055	+	* </pre>
3056	+	* except that the action is performed atomically.
3057	+	* @param key key with which the specified value is associated.
3058	+	* @param value value associated with the specified key.
3059	+	* @return true if the value was removed, false otherwise
3060	+	* @throws ClassCastException if the key cannot be compared
3061	+	* with the keys currently in the map.
3062	+	* @throws NullPointerException if the key or value are
3063	+	* <tt>null</tt>.
3064	+	*/
3065	+	public boolean remove(Object key, Object value) {
3066	+	K k = (K)key;
3067	+	return inHalfOpenRange(k) && m.remove(k, value);
3068	+	}
3069	+
3070	+	/**
3071	+	* Replace entry for key only if currently mapped to given value.
3072	+	* Acts as
3073	+	* <pre>
3074	+	*  if ((map.containsKey(key) && map.get(key).equals(oldValue)) {
3075	+	*     map.put(key, newValue);
3076	+	*     return true;
3077	+	* } else return false;
3078	+	* </pre>
3079	+	* except that the action is performed atomically.
3080	+	* @param key key with which the specified value is associated.
3081	+	* @param oldValue value expected to be associated with the specified key.
3082	+	* @param newValue value to be associated with the specified key.
3083	+	* @return true if the value was replaced
3084	+	* @throws ClassCastException if the key cannot be compared
3085	+	* with the keys currently in the map.
3086	+	* @throws IllegalArgumentException if key outside range of
3087	+	* this submap.
3088	+	* @throws NullPointerException if key, oldValue or newValue
3089	+	* are <tt>null</tt>.
3090	+	*/
3091	+	public boolean replace(K key, V oldValue, V newValue) {
3092	+	checkKey(key);
3093	+	return m.replace(key, oldValue, newValue);
3094	+	}
3095	+
3096	+	/**
3097	+	* Replace entry for key only if currently mapped to some value.
3098	+	* Acts as
3099	+	* <pre>
3100	+	*  if ((map.containsKey(key)) {
3101	+	*     return map.put(key, value);
3102	+	* } else return null;
3103	+	* </pre>
3104	+	* except that the action is performed atomically.
3105	+	* @param key key with which the specified value is associated.
3106	+	* @param value value to be associated with the specified key.
3107	+	* @return previous value associated with specified key, or
3108	+	* <tt>null</tt> if there was no mapping for key.
3109	+	* @throws ClassCastException if the key cannot be compared
3110	+	* with the keys currently in the map.
3111	+	* @throws IllegalArgumentException if key outside range of
3112	+	* this submap.
3113	+	* @throws NullPointerException if the key or value are
3114	+	* <tt>null</tt>.
3115	+	*/
3116	+	public V replace(K key, V value) {
3117	+	checkKey(key);
3118	+	return m.replace(key, value);
3119	+	}
3120	+
3121	+	/* ----------------  SortedMap API methods -------------- */
3122	+
3123	+	/**
3124	+	* Returns the comparator used to order this map, or <tt>null</tt>
3125	+	* if this map uses its keys' natural order.
3126	+	*
3127	+	* @return the comparator associated with this map, or
3128	+	* <tt>null</tt> if it uses its keys' natural sort method.
3129	+	*/
3130	+	public Comparator<? super K> comparator() {
3131	+	return m.comparator();
3132	+	}
3133	+
3134	+	/**
3135	+	* Returns the first (lowest) key currently in this map.
3136	+	*
3137	+	* @return the first (lowest) key currently in this map.
3138	+	* @throws    NoSuchElementException Map is empty.
3139	+	*/
3140	+	public K firstKey() {
3141	+	ConcurrentSkipListMap.Node<K,V> n = firstNode();
3142	+	if (isBeforeEnd(n))
3143	+	return n.key;
3144	+	else
3145	+	throw new NoSuchElementException();
3146	+	}
3147	+
3148	+	/**
3149	+	* Returns the last (highest) key currently in this map.
3150	+	*
3151	+	* @return the last (highest) key currently in this map.
3152	+	* @throws    NoSuchElementException Map is empty.
3153	+	*/
3154	+	public K lastKey() {
3155	+	ConcurrentSkipListMap.Node<K,V> n = lastNode();
3156	+	if (n != null) {
3157	+	K last = n.key;
3158	+	if (inHalfOpenRange(last))
3159	+	return last;
3160	+	}
3161	+	throw new NoSuchElementException();
3162	+	}
3163	+
3164	+	/**
3165	+	* Returns a view of the portion of this map whose keys range
3166	+	* from <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>,
3167	+	* exclusive.  (If <tt>fromKey</tt> and <tt>toKey</tt> are
3168	+	* equal, the returned sorted map is empty.)  The returned
3169	+	* sorted map is backed by this map, so changes in the
3170	+	* returned sorted map are reflected in this map, and
3171	+	* vice-versa.
3172	+
3173	+	* @param fromKey low endpoint (inclusive) of the subMap.
3174	+	* @param toKey high endpoint (exclusive) of the subMap.
3175	+	*
3176	+	* @return a view of the portion of this map whose keys range
3177	+	* from <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>,
3178	+	* exclusive.
3179	+	*
3180	+	* @throws ClassCastException if <tt>fromKey</tt> and
3181	+	* <tt>toKey</tt> cannot be compared to one another using this
3182	+	* map's comparator (or, if the map has no comparator, using
3183	+	* natural ordering).
3184	+	* @throws IllegalArgumentException if <tt>fromKey</tt> is
3185	+	* greater than <tt>toKey</tt> or either key is outside of
3186	+	* the range of this submap.
3187	+	* @throws NullPointerException if <tt>fromKey</tt> or
3188	+	* <tt>toKey</tt> is <tt>null</tt>.
3189	+	*/
3190	+	public ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey) {
3191	+	if (fromKey == null || toKey == null)
3192	+	throw new NullPointerException();
3193	+	if (!inOpenRange(fromKey) || !inOpenRange(toKey))
3194	+	throw new IllegalArgumentException("key out of range");
3195	+	return new ConcurrentSkipListSubMap(m, fromKey, toKey);
3196	+	}
3197	+
3198	+	/**
3199	+	* Returns a view of the portion of this map whose keys are
3200	+	* strictly less than <tt>toKey</tt>.  The returned sorted map
3201	+	* is backed by this map, so changes in the returned sorted
3202	+	* map are reflected in this map, and vice-versa.
3203	+	* @param toKey high endpoint (exclusive) of the headMap.
3204	+	* @return a view of the portion of this map whose keys are
3205	+	* strictly less than <tt>toKey</tt>.
3206	+	*
3207	+	* @throws ClassCastException if <tt>toKey</tt> is not
3208	+	* compatible with this map's comparator (or, if the map has
3209	+	* no comparator, if <tt>toKey</tt> does not implement
3210	+	* <tt>Comparable</tt>).
3211	+	* @throws IllegalArgumentException if <tt>toKey</tt> is
3212	+	* outside of the range of this submap.
3213	+	* @throws NullPointerException if <tt>toKey</tt> is
3214	+	* <tt>null</tt>.
3215	+	*/
3216	+	public ConcurrentNavigableMap<K,V> headMap(K toKey) {
3217	+	if (toKey == null)
3218	+	throw new NullPointerException();
3219	+	if (!inOpenRange(toKey))
3220	+	throw new IllegalArgumentException("key out of range");
3221	+	return new ConcurrentSkipListSubMap(m, least, toKey);
3222	+	}
3223	+
3224	+	/**
3225	+	* Returns a view of the portion of this map whose keys are
3226	+	* greater than or equal to <tt>fromKey</tt>.  The returned sorted
3227	+	* map is backed by this map, so changes in the returned sorted
3228	+	* map are reflected in this map, and vice-versa.
3229	+	* @param fromKey low endpoint (inclusive) of the tailMap.
3230	+	* @return a view of the portion of this map whose keys are
3231	+	* greater than or equal to <tt>fromKey</tt>.
3232	+	* @throws ClassCastException if <tt>fromKey</tt> is not
3233	+	* compatible with this map's comparator (or, if the map has
3234	+	* no comparator, if <tt>fromKey</tt> does not implement
3235	+	* <tt>Comparable</tt>).
3236	+	* @throws IllegalArgumentException if <tt>fromKey</tt> is
3237	+	* outside of the range of this submap.
3238	+	* @throws NullPointerException if <tt>fromKey</tt> is
3239	+	* <tt>null</tt>.
3240	+	*/
3241	+	public  ConcurrentNavigableMap<K,V> tailMap(K fromKey) {
3242	+	if (fromKey == null)
3243	+	throw new NullPointerException();
3244	+	if (!inOpenRange(fromKey))
3245	+	throw new IllegalArgumentException("key out of range");
3246	+	return new ConcurrentSkipListSubMap(m, fromKey, fence);
3247	+	}
3248	+
3249	+	/* ----------------  Relational methods -------------- */
3250	+
3251	+	/**
3252	+	* Returns a key-value mapping associated with the least key
3253	+	* greater than or equal to the given key, or null if there is
3254	+	* no such entry. The returned entry does <em>not</em> support
3255	+	* the <tt>Entry.setValue</tt> method.
3256	+	*
3257	+	* @param key the key.
3258	+	* @return an Entry associated with ceiling of given key, or null
3259	+	* if there is no such Entry.
3260	+	* @throws ClassCastException if key cannot be compared with the keys
3261	+	*            currently in the map.
3262	+	* @throws NullPointerException if key is <tt>null</tt>.
3263	+	*/
3264	+	public Map.Entry<K,V> ceilingEntry(K key) {
3265	+	return m.getCeiling(key, least, fence);
3266	+	}
3267	+
3268	+	/**
3269	+	* Returns a key-value mapping associated with the greatest
3270	+	* key strictly less than the given key, or null if there is no
3271	+	* such entry. The returned entry does <em>not</em> support
3272	+	* the <tt>Entry.setValue</tt> method.
3273	+	*
3274	+	* @param key the key.
3275	+	* @return an Entry with greatest key less than the given
3276	+	* key, or null if there is no such Entry.
3277	+	* @throws ClassCastException if key cannot be compared with the keys
3278	+	*            currently in the map.
3279	+	* @throws NullPointerException if key is <tt>null</tt>.
3280	+	*/
3281	+	public Map.Entry<K,V> lowerEntry(K key) {
3282	+	return m.getLower(key, least, fence);
3283	+	}
3284	+
3285	+	/**
3286	+	* Returns a key-value mapping associated with the greatest
3287	+	* key less than or equal to the given key, or null if there is no
3288	+	* such entry. The returned entry does <em>not</em> support
3289	+	* the <tt>Entry.setValue</tt> method.
3290	+	*
3291	+	* @param key the key.
3292	+	* @return an Entry associated with floor of given key, or null
3293	+	* if there is no such Entry.
3294	+	* @throws ClassCastException if key cannot be compared with the keys
3295	+	*            currently in the map.
3296	+	* @throws NullPointerException if key is <tt>null</tt>.
3297	+	*/
3298	+	public Map.Entry<K,V> floorEntry(K key) {
3299	+	return m.getFloor(key, least, fence);
3300	+	}
3301	+
3302	+	/**
3303	+	* Returns a key-value mapping associated with the least
3304	+	* key strictly greater than the given key, or null if there is no
3305	+	* such entry. The returned entry does <em>not</em> support
3306	+	* the <tt>Entry.setValue</tt> method.
3307	+	*
3308	+	* @param key the key.
3309	+	* @return an Entry with least key greater than the given key, or
3310	+	* null if there is no such Entry.
3311	+	* @throws ClassCastException if key cannot be compared with the keys
3312	+	*            currently in the map.
3313	+	* @throws NullPointerException if key is <tt>null</tt>.
3314	+	*/
3315	+	public Map.Entry<K,V> higherEntry(K key) {
3316	+	return m.getHigher(key, least, fence);
3317	+	}
3318	+
3319	+	/**
3320	+	* Returns a key-value mapping associated with the least
3321	+	* key in this map, or null if the map is empty.
3322	+	* The returned entry does <em>not</em> support
3323	+	* the <tt>Entry.setValue</tt> method.
3324	+	*
3325	+	* @return an Entry with least key, or null
3326	+	* if the map is empty.
3327	+	*/
3328	+	public Map.Entry<K,V> firstEntry() {
3329	+	for (;;) {
3330	+	ConcurrentSkipListMap.Node<K,V> n = firstNode();
3331	+	if (!isBeforeEnd(n))
3332	+	return null;
3333	+	Map.Entry<K,V> e = n.createSnapshot();
3334	+	if (e != null)
3335	+	return e;
3336	+	}
3337	+	}
3338	+
3339	+	/**
3340	+	* Returns a key-value mapping associated with the greatest
3341	+	* key in this map, or null if the map is empty.
3342	+	* The returned entry does <em>not</em> support
3343	+	* the <tt>Entry.setValue</tt> method.
3344	+	*
3345	+	* @return an Entry with greatest key, or null
3346	+	* if the map is empty.
3347	+	*/
3348	+	public Map.Entry<K,V> lastEntry() {
3349	+	for (;;) {
3350	+	ConcurrentSkipListMap.Node<K,V> n = lastNode();
3351	+	if (n == null || !inHalfOpenRange(n.key))
3352	+	return null;
3353	+	Map.Entry<K,V> e = n.createSnapshot();
3354	+	if (e != null)
3355	+	return e;
3356	+	}
3357	+	}
3358	+
3359	+	/**
3360	+	* Removes and returns a key-value mapping associated with
3361	+	* the least key in this map, or null if the map is empty.
3362	+	* The returned entry does <em>not</em> support
3363	+	* the <tt>Entry.setValue</tt> method.
3364	+	*
3365	+	* @return the removed first entry of this map, or null
3366	+	* if the map is empty.
3367	+	*/
3368	+	public Map.Entry<K,V> pollFirstEntry() {
3369	+	return m.removeFirstEntryOfSubrange(least, fence);
3370	+	}
3371	+
3372	+	/**
3373	+	* Removes and returns a key-value mapping associated with
3374	+	* the greatest key in this map, or null if the map is empty.
3375	+	* The returned entry does <em>not</em> support
3376	+	* the <tt>Entry.setValue</tt> method.
3377	+	*
3378	+	* @return the removed last entry of this map, or null
3379	+	* if the map is empty.
3380	+	*/
3381	+	public Map.Entry<K,V> pollLastEntry() {
3382	+	return m.removeLastEntryOfSubrange(least, fence);
3383	+	}
3384	+
3385	+	/* ---------------- Submap Views -------------- */
3386	+
3387	+	/**
3388	+	* Returns a set view of the keys contained in this map.  The
3389	+	* set is backed by the map, so changes to the map are
3390	+	* reflected in the set, and vice-versa.  The set supports
3391	+	* element removal, which removes the corresponding mapping
3392	+	* from this map, via the <tt>Iterator.remove</tt>,
3393	+	* <tt>Set.remove</tt>, <tt>removeAll</tt>,
3394	+	* <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does
3395	+	* not support the <tt>add</tt> or <tt>addAll</tt> operations.
3396	+	* The view's <tt>iterator</tt> is a "weakly consistent"
3397	+	* iterator that will never throw {@link
3398	+	* java.util.ConcurrentModificationException}, and guarantees
3399	+	* to traverse elements as they existed upon construction of
3400	+	* the iterator, and may (but is not guaranteed to) reflect
3401	+	* any modifications subsequent to construction.
3402	+	*
3403	+	* @return a set view of the keys contained in this map.
3404	+	*/
3405	+	public Set<K> keySet() {
3406	+	Set<K> ks = keySetView;
3407	+	return (ks != null) ? ks : (keySetView = new KeySetView());
3408	+	}
3409	+
3410	+	class KeySetView extends AbstractSet<K> {
3411	+	public Iterator<K> iterator() {
3412	+	return m.subMapKeyIterator(least, fence);
3413	+	}
3414	+	public int size() {
3415	+	return ConcurrentSkipListSubMap.this.size();
3416	+	}
3417	+	public boolean isEmpty() {
3418	+	return ConcurrentSkipListSubMap.this.isEmpty();
3419	+	}
3420	+	public boolean contains(Object k) {
3421	+	return ConcurrentSkipListSubMap.this.containsKey(k);
3422	+	}
3423	+	public Object[] toArray() {
3424	+	Collection<K> c = new ArrayList<K>();
3425	+	for (Iterator<K> i = iterator(); i.hasNext(); )
3426	+	c.add(i.next());
3427	+	return c.toArray();
3428	+	}
3429	+	public <T> T[] toArray(T[] a) {
3430	+	Collection<K> c = new ArrayList<K>();
3431	+	for (Iterator<K> i = iterator(); i.hasNext(); )
3432	+	c.add(i.next());
3433	+	return c.toArray(a);
3434	+	}
3435	+	}
3436	+
3437	+	/**
3438	+	* Returns a collection view of the values contained in this
3439	+	* map.  The collection is backed by the map, so changes to
3440	+	* the map are reflected in the collection, and vice-versa.
3441	+	* The collection supports element removal, which removes the
3442	+	* corresponding mapping from this map, via the
3443	+	* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
3444	+	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
3445	+	* operations.  It does not support the <tt>add</tt> or
3446	+	* <tt>addAll</tt> operations.  The view's <tt>iterator</tt>
3447	+	* is a "weakly consistent" iterator that will never throw
3448	+	* {@link java.util.ConcurrentModificationException}, and
3449	+	* guarantees to traverse elements as they existed upon
3450	+	* construction of the iterator, and may (but is not
3451	+	* guaranteed to) reflect any modifications subsequent to
3452	+	* construction.
3453	+	*
3454	+	* @return a collection view of the values contained in this map.
3455	+	*/
3456	+	public Collection<V> values() {
3457	+	Collection<V> vs = valuesView;
3458	+	return (vs != null) ? vs : (valuesView = new ValuesView());
3459	+	}
3460	+
3461	+	class ValuesView extends AbstractCollection<V> {
3462	+	public Iterator<V> iterator() {
3463	+	return m.subMapValueIterator(least, fence);
3464	+	}
3465	+	public int size() {
3466	+	return ConcurrentSkipListSubMap.this.size();
3467	+	}
3468	+	public boolean isEmpty() {
3469	+	return ConcurrentSkipListSubMap.this.isEmpty();
3470	+	}
3471	+	public boolean contains(Object v) {
3472	+	return ConcurrentSkipListSubMap.this.containsValue(v);
3473	+	}
3474	+	public Object[] toArray() {
3475	+	Collection<V> c = new ArrayList<V>();
3476	+	for (Iterator<V> i = iterator(); i.hasNext(); )
3477	+	c.add(i.next());
3478	+	return c.toArray();
3479	+	}
3480	+	public <T> T[] toArray(T[] a) {
3481	+	Collection<V> c = new ArrayList<V>();
3482	+	for (Iterator<V> i = iterator(); i.hasNext(); )
3483	+	c.add(i.next());
3484	+	return c.toArray(a);
3485	+	}
3486	+	}
3487	+
3488	+	/**
3489	+	* Returns a collection view of the mappings contained in this
3490	+	* map.  Each element in the returned collection is a
3491	+	* <tt>Map.Entry</tt>.  The collection is backed by the map,
3492	+	* so changes to the map are reflected in the collection, and
3493	+	* vice-versa.  The collection supports element removal, which
3494	+	* removes the corresponding mapping from the map, via the
3495	+	* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
3496	+	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
3497	+	* operations.  It does not support the <tt>add</tt> or
3498	+	* <tt>addAll</tt> operations.  The view's <tt>iterator</tt>
3499	+	* is a "weakly consistent" iterator that will never throw
3500	+	* {@link java.util.ConcurrentModificationException}, and
3501	+	* guarantees to traverse elements as they existed upon
3502	+	* construction of the iterator, and may (but is not
3503	+	* guaranteed to) reflect any modifications subsequent to
3504	+	* construction. The <tt>Map.Entry</tt> elements returned by
3505	+	* <tt>iterator.next()</tt> do <em>not</em> support the
3506	+	* <tt>setValue</tt> operation.
3507	+	*
3508	+	* @return a collection view of the mappings contained in this map.
3509	+	*/
3510	+	public Set<Map.Entry<K,V>> entrySet() {
3511	+	Set<Map.Entry<K,V>> es = entrySetView;
3512	+	return (es != null) ? es : (entrySetView = new EntrySetView());
3513	+	}
3514	+
3515	+	class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
3516	+	public Iterator<Map.Entry<K,V>> iterator() {
3517	+	return m.subMapEntryIterator(least, fence);
3518	+	}
3519	+	public int size() {
3520	+	return ConcurrentSkipListSubMap.this.size();
3521	+	}
3522	+	public boolean isEmpty() {
3523	+	return ConcurrentSkipListSubMap.this.isEmpty();
3524	+	}
3525	+	public boolean contains(Object o) {
3526	+	if (!(o instanceof Map.Entry))
3527	+	return false;
3528	+	Map.Entry<K,V> e = (Map.Entry<K,V>) o;
3529	+	K key = e.getKey();
3530	+	if (!inHalfOpenRange(key))
3531	+	return false;
3532	+	V v = m.get(key);
3533	+	return v != null && v.equals(e.getValue());
3534	+	}
3535	+	public boolean remove(Object o) {
3536	+	if (!(o instanceof Map.Entry))
3537	+	return false;
3538	+	Map.Entry<K,V> e = (Map.Entry<K,V>) o;
3539	+	K key = e.getKey();
3540	+	if (!inHalfOpenRange(key))
3541	+	return false;
3542	+	return m.remove(key, e.getValue());
3543	+	}
3544	+	public Object[] toArray() {
3545	+	Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>();
3546	+	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3547	+	isBeforeEnd(n);
3548	+	n = n.next) {
3549	+	Map.Entry<K,V> e = n.createSnapshot();
3550	+	if (e != null)
3551	+	c.add(e);
3552	+	}
3553	+	return c.toArray();
3554	+	}
3555	+	public <T> T[] toArray(T[] a) {
3556	+	Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>();
3557	+	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3558	+	isBeforeEnd(n);
3559	+	n = n.next) {
3560	+	Map.Entry<K,V> e = n.createSnapshot();
3561	+	if (e != null)
3562	+	c.add(e);
3563	+	}
3564	+	return c.toArray(a);
3565	+	}
3566	+	}
3567	+	}
3568	+
3569		}

Diff Legend

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