ViewVC Help

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

root/jsr166/jsr166/src/jsr166x/ConcurrentSkipListSet.java

Comparing jsr166/src/jsr166x/ConcurrentSkipListSet.java (file contents):
Revision 1.5 by dl, Tue Dec 21 17:27:44 2004 UTC vs.
Revision 1.13 by jsr166, Mon Dec 19 19:18:36 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;
7	>	package jsr166x;
8
9		import java.util.*;
10		import java.util.concurrent.*;
#	Line 24 | Line 24 | import java.util.concurrent.*;
24		* threads. Iterators are <i>weakly consistent</i>, returning elements
25		* reflecting the state of the set at some point at or since the
26		* creation of the iterator.  They do <em>not</em> throw {@link
27	<	* ConcurrentModificationException}, and may procede concurrently with
27	>	* ConcurrentModificationException}, and may proceed concurrently with
28		* other operations.
29		*
30		* <p>Beware that, unlike in most collections, the <tt>size</tt>
#	Line 60 | Line 60 | public class ConcurrentSkipListSet<E>
60		* fields of underlying map, but enables this field to be declared
61		* final, which is necessary for thread safety.
62		*/
63	<	private final ConcurrentSkipListMap<E,Object> m;
63	>	private final ConcurrentSkipListMap<E,Object> m;
64
65		/**
66		* Constructs a new, empty set, sorted according to the elements' natural
67	<	* order.
67	>	* order.
68		*/
69		public ConcurrentSkipListSet() {
70		m = new ConcurrentSkipListMap<E,Object>();
#	Line 72 | Line 72 | public class ConcurrentSkipListSet<E>
72
73		/**
74		* Constructs a new, empty set, sorted according to the specified
75	<	* comparator.
75	>	* comparator.
76		*
77		* @param c the comparator that will be used to sort this set.  A
78		*        <tt>null</tt> value indicates that the elements' <i>natural
#	Line 119 | Line 119 | public class ConcurrentSkipListSet<E>
119		*/
120		public Object clone() {
121		ConcurrentSkipListSet<E> clone = null;
122	<	try {
123	<	clone = (ConcurrentSkipListSet<E>) super.clone();
124	<	} catch (CloneNotSupportedException e) {
125	<	throw new InternalError();
126	<	}
122	>	try {
123	>	clone = (ConcurrentSkipListSet<E>) super.clone();
124	>	} catch (CloneNotSupportedException e) {
125	>	throw new InternalError();
126	>	}
127
128		clone.m.initialize();
129		clone.addAll(this);
#	Line 149 | Line 149 | public class ConcurrentSkipListSet<E>
149		* @return  the number of elements in this set.
150		*/
151		public int size() {
152	<	return m.size();
152	>	return m.size();
153		}
154
155		/**
#	Line 157 | Line 157 | public class ConcurrentSkipListSet<E>
157		* @return <tt>true</tt> if this set contains no elements.
158		*/
159		public boolean isEmpty() {
160	<	return m.isEmpty();
160	>	return m.isEmpty();
161		}
162
163		/**
#	Line 167 | Line 167 | public class ConcurrentSkipListSet<E>
167		* @return <tt>true</tt> if this set contains the specified element.
168		*
169		* @throws ClassCastException if the specified object cannot be compared
170	<	*            with the elements currently in the set.
170	>	*            with the elements currently in the set.
171		* @throws NullPointerException if o is <tt>null</tt>.
172		*/
173		public boolean contains(Object o) {
174	<	return m.containsKey(o);
174	>	return m.containsKey(o);
175		}
176
177		/**
#	Line 182 | Line 182 | public class ConcurrentSkipListSet<E>
182		*         element.
183		*
184		* @throws ClassCastException if the specified object cannot be compared
185	<	*            with the elements currently in the set.
185	>	*            with the elements currently in the set.
186		* @throws NullPointerException if o is <tt>null</tt>.
187		*/
188		public boolean add(E o) {
189	<	return m.putIfAbsent(o, Boolean.TRUE) == null;
189	>	return m.putIfAbsent(o, Boolean.TRUE) == null;
190		}
191
192		/**
#	Line 196 | Line 196 | public class ConcurrentSkipListSet<E>
196		* @return <tt>true</tt> if the set contained the specified element.
197		*
198		* @throws ClassCastException if the specified object cannot be compared
199	<	*            with the elements currently in the set.
199	>	*            with the elements currently in the set.
200		* @throws NullPointerException if o is <tt>null</tt>.
201		*/
202		public boolean remove(Object o) {
203	<	return m.removep(o);
203	>	return m.removep(o);
204		}
205
206		/**
207		* Removes all of the elements from this set.
208		*/
209		public void clear() {
210	<	m.clear();
210	>	m.clear();
211		}
212
213		/**
#	Line 217 | Line 217 | public class ConcurrentSkipListSet<E>
217		* @return an iterator over the elements in this set.
218		*/
219		public Iterator<E> iterator() {
220	<	return m.keyIterator();
220	>	return m.keyIterator();
221		}
222
223		/**
#	Line 227 | Line 227 | public class ConcurrentSkipListSet<E>
227		* @return an iterator over the elements in this set.
228		*/
229		public Iterator<E> descendingIterator() {
230	<	return m.descendingKeyIterator();
230	>	return m.descendingKeyIterator();
231		}
232
233		/* ---------------- AbstractSet Overrides -------------- */
#	Line 246 | Line 246 | public class ConcurrentSkipListSet<E>
246		*/
247		public boolean equals(Object o) {
248		// Override AbstractSet version to avoid calling size()
249	<	if (o == this)
250	<	return true;
251	<	if (!(o instanceof Set))
252	<	return false;
253	<	Collection c = (Collection) o;
249	>	if (o == this)
250	>	return true;
251	>	if (!(o instanceof Set))
252	>	return false;
253	>	Collection c = (Collection) o;
254		try {
255		return containsAll(c) && c.containsAll(this);
256	<	} catch(ClassCastException unused)   {
256	>	} catch (ClassCastException unused) {
257		return false;
258	<	} catch(NullPointerException unused) {
258	>	} catch (NullPointerException unused) {
259		return false;
260		}
261		}
262	<
262	>
263		/**
264		* Removes from this set all of its elements that are contained in
265		* the specified collection.  If the specified collection is also
#	Line 269 | Line 269 | public class ConcurrentSkipListSet<E>
269		* @param  c collection that defines which elements will be removed from
270		*           this set.
271		* @return <tt>true</tt> if this set changed as a result of the call.
272	<	*
272	>	*
273		* @throws ClassCastException if the types of one or more elements in this
274		*            set are incompatible with the specified collection
275		* @throws NullPointerException if the specified collection, or any
#	Line 283 | Line 283 | public class ConcurrentSkipListSet<E>
283		modified = true;
284		return modified;
285		}
286	<
286	>
287		/* ---------------- Relational operations -------------- */
288
289		/**
290		* Returns an element greater than or equal to the given element, or
291		* <tt>null</tt> if there is no such element.
292	<	*
292	>	*
293		* @param o the value to match
294		* @return an element greater than or equal to given element, or
295		* <tt>null</tt> if there is no such element.
#	Line 304 | Line 304 | public class ConcurrentSkipListSet<E>
304		/**
305		* Returns an element strictly less than the given element, or
306		* <tt>null</tt> if there is no such element.
307	<	*
307	>	*
308		* @param o the value to match
309		* @return the greatest element less than the given element, or
310		* <tt>null</tt> if there is no such element.
#	Line 319 | Line 319 | public class ConcurrentSkipListSet<E>
319		/**
320		* Returns an element less than or equal to the given element, or
321		* <tt>null</tt> if there is no such element.
322	<	*
322	>	*
323		* @param o the value to match
324		* @return the greatest element less than or equal to given
325		* element, or <tt>null</tt> if there is no such element.
#	Line 334 | Line 334 | public class ConcurrentSkipListSet<E>
334		/**
335		* Returns an element strictly greater than the given element, or
336		* <tt>null</tt> if there is no such element.
337	<	*
337	>	*
338		* @param o the value to match
339		* @return the least element greater than the given element, or
340		* <tt>null</tt> if there is no such element.
#	Line 407 | Line 407 | public class ConcurrentSkipListSet<E>
407		* <tt>fromElement</tt> and <tt>toElement</tt> are equal, the returned
408		* sorted set is empty.)  The returned sorted set is backed by this set,
409		* so changes in the returned sorted set are reflected in this set, and
410	<	* vice-versa.
410	>	* vice-versa.
411		* @param fromElement low endpoint (inclusive) of the subSet.
412		* @param toElement high endpoint (exclusive) of the subSet.
413		* @return a view of the portion of this set whose elements range from
414	<	*         <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>,
415	<	*         exclusive.
414	>	*         <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>,
415	>	*         exclusive.
416		* @throws ClassCastException if <tt>fromElement</tt> and
417		*         <tt>toElement</tt> cannot be compared to one another using
418		*         this set's comparator (or, if the set has no comparator,
#	Line 420 | Line 420 | public class ConcurrentSkipListSet<E>
420		* @throws IllegalArgumentException if <tt>fromElement</tt> is
421		* greater than <tt>toElement</tt>.
422		* @throws NullPointerException if <tt>fromElement</tt> or
423	<	*         <tt>toElement</tt> is <tt>null</tt>.
423	>	*         <tt>toElement</tt> is <tt>null</tt>.
424		*/
425		public NavigableSet<E> subSet(E fromElement, E toElement) {
426	<	return new ConcurrentSkipListSubSet<E>(m, fromElement, toElement);
426	>	return new ConcurrentSkipListSubSet<E>(m, fromElement, toElement);
427		}
428
429		/**
430		* Returns a view of the portion of this set whose elements are strictly
431		* less than <tt>toElement</tt>.  The returned sorted set is backed by
432		* this set, so changes in the returned sorted set are reflected in this
433	<	* set, and vice-versa.
433	>	* set, and vice-versa.
434		* @param toElement high endpoint (exclusive) of the headSet.
435		* @return a view of the portion of this set whose elements are strictly
436	<	*         less than toElement.
436	>	*         less than toElement.
437		* @throws ClassCastException if <tt>toElement</tt> is not compatible
438		*         with this set's comparator (or, if the set has no comparator,
439		*         if <tt>toElement</tt> does not implement <tt>Comparable</tt>).
440		* @throws NullPointerException if <tt>toElement</tt> is <tt>null</tt>.
441		*/
442		public NavigableSet<E> headSet(E toElement) {
443	<	return new ConcurrentSkipListSubSet<E>(m, null, toElement);
443	>	return new ConcurrentSkipListSubSet<E>(m, null, toElement);
444		}
445
446
#	Line 459 | Line 459 | public class ConcurrentSkipListSet<E>
459		* @throws NullPointerException if <tt>fromElement</tt> is <tt>null</tt>.
460		*/
461		public NavigableSet<E> tailSet(E fromElement) {
462	<	return new ConcurrentSkipListSubSet<E>(m, fromElement, null);
462	>	return new ConcurrentSkipListSubSet<E>(m, fromElement, null);
463		}
464
465		/**
#	Line 473 | Line 473 | public class ConcurrentSkipListSet<E>
473		* <tt>tailSet</tt> methods of their underlying sets.
474		*
475		*/
476	<	static class ConcurrentSkipListSubSet<E>
477	<	extends AbstractSet<E>
476	>	static class ConcurrentSkipListSubSet<E>
477	>	extends AbstractSet<E>
478		implements NavigableSet<E>, java.io.Serializable {
479
480		private static final long serialVersionUID = -7647078645896651609L;
481
482		/** The underlying submap  */
483		private final ConcurrentSkipListMap.ConcurrentSkipListSubMap<E,Object> s;
484	<
484	>
485		/**
486	<	* Creates a new submap.
486	>	* Creates a new submap.
487		* @param fromElement inclusive least value, or <tt>null</tt> if from start
488		* @param toElement exclusive upper bound or <tt>null</tt> if to end
489		* @throws IllegalArgumentException if fromElement and toElement
490	<	* nonnull and fromElement greater than toElement
490	>	* non-null and fromElement greater than toElement
491		*/
492	<	ConcurrentSkipListSubSet(ConcurrentSkipListMap<E,Object> map,
492	>	ConcurrentSkipListSubSet(ConcurrentSkipListMap<E,Object> map,
493		E fromElement, E toElement) {
494		s = new ConcurrentSkipListMap.ConcurrentSkipListSubMap<E,Object>
495		(map, fromElement, toElement);
#	Line 500 | Line 500 | public class ConcurrentSkipListSet<E>
500		public NavigableSet<E> subSet(E fromElement, E toElement) {
501		if (!s.inOpenRange(fromElement) || !s.inOpenRange(toElement))
502		throw new IllegalArgumentException("element out of range");
503	<	return new ConcurrentSkipListSubSet<E>(s.getMap(),
503	>	return new ConcurrentSkipListSubSet<E>(s.getMap(),
504		fromElement, toElement);
505		}
506
#	Line 508 | Line 508 | public class ConcurrentSkipListSet<E>
508		E least = s.getLeast();
509		if (!s.inOpenRange(toElement))
510		throw new IllegalArgumentException("element out of range");
511	<	return new ConcurrentSkipListSubSet<E>(s.getMap(),
511	>	return new ConcurrentSkipListSubSet<E>(s.getMap(),
512		least, toElement);
513		}
514	<
514	>
515		public NavigableSet<E> tailSet(E fromElement) {
516		E fence = s.getFence();
517		if (!s.inOpenRange(fromElement))
518		throw new IllegalArgumentException("element out of range");
519	<	return new ConcurrentSkipListSubSet<E>(s.getMap(),
519	>	return new ConcurrentSkipListSubSet<E>(s.getMap(),
520		fromElement, fence);
521		}
522
#	Line 539 | Line 539 | public class ConcurrentSkipListSet<E>
539		public Iterator<E> descendingIterator() {
540		return s.descendingKeySet().iterator();
541		}
542	<	public E pollFirst() {
542	>	public E pollFirst() {
543		Map.Entry<E,?> e = s.pollFirstEntry();
544	<	return (e == null)? null : e.getKey();
544	>	return (e == null) ? null : e.getKey();
545		}
546		public E pollLast() {
547		Map.Entry<E,?> e = s.pollLastEntry();
548	<	return (e == null)? null : e.getKey();
548	>	return (e == null) ? null : e.getKey();
549		}
550
551		}
552	<	}
552	>	}

Diff Legend

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