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.8 by jsr166, Mon Nov 16 04:16:42 2009 UTC vs.
Revision 1.15 by jsr166, Tue Oct 25 18:46:37 2011 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 583 | Line 583 | public class ConcurrentSkipListMap<K,V>
583		* support the <tt>Map.Entry.setValue</tt> method.
584		*/
585		static class SnapshotEntry<K,V> implements Map.Entry<K,V> {
586	<	private final K key;
587	<	private final V value;
586	>	private final K key;
587	>	private final V value;
588
589		/**
590		* Creates a new entry representing the given key and value.
#	Line 592 | Line 592 | public class ConcurrentSkipListMap<K,V>
592		* @param value the value
593		*/
594		SnapshotEntry(K key, V value) {
595	<	this.key = key;
596	<	this.value = value;
597	<	}
598	<
599	<	/**
600	<	* Returns the key corresponding to this entry.
601	<	*
602	<	* @return the key corresponding to this entry.
603	<	*/
595	>	this.key = key;
596	>	this.value = value;
597	>	}
598	>
599	>	/**
600	>	* Returns the key corresponding to this entry.
601	>	*
602	>	* @return the key corresponding to this entry.
603	>	*/
604		public K getKey() {
605		return key;
606		}
607
608	<	/**
609	<	* Returns the value corresponding to this entry.
610	<	*
611	<	* @return the value corresponding to this entry.
612	<	*/
608	>	/**
609	>	* Returns the value corresponding to this entry.
610	>	*
611	>	* @return the value corresponding to this entry.
612	>	*/
613		public V getValue() {
614	<	return value;
614	>	return value;
615		}
616
617	<	/**
618	<	* Always fails, throwing <tt>UnsupportedOperationException</tt>.
619	<	* @throws UnsupportedOperationException always.
617	>	/**
618	>	* Always fails, throwing <tt>UnsupportedOperationException</tt>.
619	>	* @throws UnsupportedOperationException always.
620		*/
621		public V setValue(V value) {
622		throw new UnsupportedOperationException();
#	Line 649 | Line 649 | public class ConcurrentSkipListMap<K,V>
649		* @return a String representation of this entry.
650		*/
651		public String toString() {
652	<	return getKey() + "=" + getValue();
652	>	return getKey() + "=" + getValue();
653		}
654		}
655
#	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 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
#	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 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 1476 | Line 1476 | public class ConcurrentSkipListMap<K,V>
1476		* Return 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>
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		/**
#	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
#	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
#	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 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 1847 | Line 1847 | public class ConcurrentSkipListMap<K,V>
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.
1850	>	*          <tt>false</tt> otherwise.
1851		* @throws  NullPointerException  if the value is <tt>null</tt>.
1852		*/
1853		public boolean containsValue(Object value) {
#	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		/**
#	Line 2056 | Line 2056 | public class ConcurrentSkipListMap<K,V>
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)
2060	<	return true;
2061	<	if (!(o instanceof Map))
2062	<	return false;
2063	<	Map<K,V> t = (Map<K,V>) o;
2059	>	if (o == this)
2060	>	return true;
2061	>	if (!(o instanceof Map))
2062	>	return false;
2063	>	Map<K,V> t = (Map<K,V>) o;
2064		try {
2065		return (containsAllMappings(this, t) &&
2066		containsAllMappings(t, this));
2067	<	} catch(ClassCastException unused) {
2067	>	} catch (ClassCastException unused) {
2068		return false;
2069	<	} catch(NullPointerException unused) {
2069	>	} catch (NullPointerException unused) {
2070		return false;
2071		}
2072		}
#	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	<
2253	>	*
2254		* @param fromKey low endpoint (inclusive) of the subMap.
2255		* @param toKey high endpoint (exclusive) of the subMap.
2256		*
#	Line 2343 | Line 2343 | public class ConcurrentSkipListMap<K,V>
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 2376 | Line 2376 | public class ConcurrentSkipListMap<K,V>
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 2410 | Line 2410 | public class ConcurrentSkipListMap<K,V>
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 2443 | Line 2443 | public class ConcurrentSkipListMap<K,V>
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 2525 | Line 2525 | public class ConcurrentSkipListMap<K,V>
2525		Node<K,V> last;
2526		/** the next node to return from next(); */
2527		Node<K,V> next;
2528	<	/** Cache of next value field to maintain weak consistency */
2529	<	Object nextValue;
2528	>	/** Cache of next value field to maintain weak consistency */
2529	>	Object nextValue;
2530
2531		Iter() {}
2532
#	Line 2537 | Line 2537 | public class ConcurrentSkipListMap<K,V>
2537		/** initialize ascending iterator for entire range  */
2538		final void initAscending() {
2539		for (;;) {
2540	<	next = findFirst();
2540	>	next = findFirst();
2541		if (next == null)
2542		break;
2543		nextValue = next.value;
#	Line 2553 | Line 2553 | public class ConcurrentSkipListMap<K,V>
2553		*/
2554		final void initAscending(K least, K fence) {
2555		for (;;) {
2556	<	next = findCeiling(least);
2556	>	next = findCeiling(least);
2557		if (next == null)
2558		break;
2559		nextValue = next.value;
#	Line 2571 | Line 2571 | public class ConcurrentSkipListMap<K,V>
2571		if ((last = next) == null)
2572		throw new NoSuchElementException();
2573		for (;;) {
2574	<	next = next.next;
2574	>	next = next.next;
2575		if (next == null)
2576		break;
2577		nextValue = next.value;
#	Line 2587 | Line 2587 | public class ConcurrentSkipListMap<K,V>
2587		if ((last = next) == null)
2588		throw new NoSuchElementException();
2589		for (;;) {
2590	<	next = next.next;
2590	>	next = next.next;
2591		if (next == null)
2592		break;
2593		nextValue = next.value;
#	Line 2604 | Line 2604 | public class ConcurrentSkipListMap<K,V>
2604		/** initialize descending iterator for entire range  */
2605		final void initDescending() {
2606		for (;;) {
2607	<	next = findLast();
2607	>	next = findLast();
2608		if (next == null)
2609		break;
2610		nextValue = next.value;
#	Line 2621 | Line 2621 | public class ConcurrentSkipListMap<K,V>
2621		*/
2622		final void initDescending(K least, K fence) {
2623		for (;;) {
2624	<	next = findLower(fence);
2624	>	next = findLower(fence);
2625		if (next == null)
2626		break;
2627		nextValue = next.value;
#	Line 2641 | Line 2641 | public class ConcurrentSkipListMap<K,V>
2641		throw new NoSuchElementException();
2642		K k = last.key;
2643		for (;;) {
2644	<	next = findNear(k, LT);
2644	>	next = findNear(k, LT);
2645		if (next == null)
2646		break;
2647		nextValue = next.value;
#	Line 2658 | Line 2658 | public class ConcurrentSkipListMap<K,V>
2658		throw new NoSuchElementException();
2659		K k = last.key;
2660		for (;;) {
2661	<	next = findNear(k, LT);
2661	>	next = findNear(k, LT);
2662		if (next == null)
2663		break;
2664		nextValue = next.value;
#	Line 2781 | Line 2781 | public class ConcurrentSkipListMap<K,V>
2781		Object v = lastValue;
2782		if (last == null || v == null)
2783		throw new IllegalStateException();
2784	<	return (V)v;
2784	>	return (V)v;
2785		}
2786
2787		public V setValue(V value) {
#	Line 2810 | Line 2810 | public class ConcurrentSkipListMap<K,V>
2810		// If not acting as entry, just use default.
2811		if (last == null)
2812		return super.toString();
2813	<	return getKey() + "=" + getValue();
2813	>	return getKey() + "=" + getValue();
2814		}
2815		}
2816
#	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() {

Diff Legend

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