ViewVC Help

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

root/jsr166/jsr166/src/main/java/util/concurrent/CopyOnWriteArrayList.java

Comparing jsr166/src/main/java/util/concurrent/CopyOnWriteArrayList.java (file contents):
Revision 1.40 by dl, Tue May 31 13:56:31 2005 UTC vs.
Revision 1.41 by dl, Tue May 31 17:39:18 2005 UTC

#	Line 52 | Line 52 | public class CopyOnWriteArrayList<E>
52		private static final long serialVersionUID = 8673264195747942595L;
53
54		/** The array, accessed only via getArray/setArray. */
55	<	private volatile transient E[] array;
55	>	private volatile transient Object[] array;
56
57	<	private E[]  getArray()      { return array; }
58	<	private void setArray(E[] a) { array = a; }
57	>	private Object[]  getArray()           { return array; }
58	>	private void      setArray(Object[] a) { array = a; }
59
60		/**
61		* Creates an empty list.
62		*/
63		public CopyOnWriteArrayList() {
64	<	setArray((E[]) new Object[0]);
64	>	setArray(new Object[0]);
65		}
66
67		/**
#	Line 73 | Line 73 | public class CopyOnWriteArrayList<E>
73		* @throws NullPointerException if the specified collection is null
74		*/
75		public CopyOnWriteArrayList(Collection<? extends E> c) {
76	<	E[] elements = (E[]) new Object[c.size()];
76	>	Object[] elements = new Object[c.size()];
77		int size = 0;
78	<	for (Iterator<? extends E> i = c.iterator(); i.hasNext(); )
79	<	elements[size++] = i.next();
78	>	for (E e : c)
79	>	elements[size++] = e;
80		setArray(elements);
81		}
82
#	Line 105 | Line 105 | public class CopyOnWriteArrayList<E>
105		*/
106		private synchronized void copyIn(E[] toCopyIn, int first, int n) {
107		int limit = first + n;
108	<	if (limit > toCopyIn.length)
108	>	if (limit > toCopyIn.length)
109		throw new IndexOutOfBoundsException();
110	<	setArray((E[]) cloneRange(toCopyIn, first, limit, Object[].class));
110	>	setArray( cloneRange(toCopyIn, first, limit, Object[].class));
111		}
112
113		/**
#	Line 128 | Line 128 | public class CopyOnWriteArrayList<E>
128		return size() == 0;
129		}
130
131	<	/**
131	>	/**
132		* static version of indexOf, to allow repeated calls without
133	<	* needing to grab re-acquire array each time.
133	>	* needing to re-acquire array each time.
134		* @param o element to search for
135		* @param elements the array
136		* @param index first index to search
137		* @param fence one past last index to search
138		* @return index of element, or -1 if absent
139		*/
140	<	private static int indexOf(Object o, Object[] elements,
140	>	private static int indexOf(Object o, Object[] elements,
141		int index, int fence) {
142		if (o == null) {
143		for (int i = index; i < fence; i++)
#	Line 150 | Line 150 | public class CopyOnWriteArrayList<E>
150		}
151		return -1;
152		}
153	<
154	<	/**
153	>
154	>	/**
155		* static version of lastIndexOf.
156		* @param o element to search for
157		* @param elements the array
#	Line 181 | Line 181 | public class CopyOnWriteArrayList<E>
181		* @return <tt>true</tt> if this list contains the specified element
182		*/
183		public boolean contains(Object o) {
184	<	E[] elements = getArray();
184	>	Object[] elements = getArray();
185		return indexOf(o, elements, 0, elements.length) >= 0;
186		}
187
#	Line 189 | Line 189 | public class CopyOnWriteArrayList<E>
189		* {@inheritDoc}
190		*/
191		public int indexOf(Object o) {
192	<	E[] elements = getArray();
192	>	Object[] elements = getArray();
193		return indexOf(o, elements, 0, elements.length);
194		}
195
#	Line 210 | Line 210 | public class CopyOnWriteArrayList<E>
210		* @throws IndexOutOfBoundsException if the specified index is negative
211		*/
212		public int indexOf(E e, int index) {
213	<	E[] elements = getArray();
213	>	Object[] elements = getArray();
214		return indexOf(e, elements, index, elements.length);
215		}
216
#	Line 218 | Line 218 | public class CopyOnWriteArrayList<E>
218		* {@inheritDoc}
219		*/
220		public int lastIndexOf(Object o) {
221	<	E[] elements = getArray();
221	>	Object[] elements = getArray();
222		return lastIndexOf(o, elements, elements.length - 1);
223		}
224
#	Line 239 | Line 239 | public class CopyOnWriteArrayList<E>
239		*         than or equal to the current size of this list
240		*/
241		public int lastIndexOf(E e, int index) {
242	<	E[] elements = getArray();
242	>	Object[] elements = getArray();
243		return lastIndexOf(e, elements, index);
244		}
245
#	Line 251 | Line 251 | public class CopyOnWriteArrayList<E>
251		*/
252		public Object clone() {
253		try {
254	<	E[] elements = getArray();
255	<	CopyOnWriteArrayList<E> v = (CopyOnWriteArrayList<E>)super.clone();
256	<	v.setArray(clone(elements, elements.length));
257	<	return v;
254	>	return super.clone();
255		} catch (CloneNotSupportedException e) {
256		// this shouldn't happen, since we are Cloneable
257		throw new InternalError();
#	Line 319 | Line 316 | public class CopyOnWriteArrayList<E>
316		* @throws NullPointerException if the specified array is null
317		*/
318		public <T> T[] toArray(T a[]) {
319	<	E[] elements = getArray();
319	>	Object[] elements = getArray();
320		int len = elements.length;
321		if (a.length < len)
322		return (T[]) clone(elements, len, a.getClass());
#	Line 339 | Line 336 | public class CopyOnWriteArrayList<E>
336		* @throws IndexOutOfBoundsException {@inheritDoc}
337		*/
338		public E get(int index) {
339	<	return getArray()[index];
339	>	return (E)(getArray()[index]);
340		}
341
342		/**
#	Line 349 | Line 346 | public class CopyOnWriteArrayList<E>
346		* @throws IndexOutOfBoundsException {@inheritDoc}
347		*/
348		public synchronized E set(int index, E element) {
349	<	E[] elements = getArray();
349	>	Object[] elements = getArray();
350		int len = elements.length;
351	<	E oldValue = elements[index];
351	>	Object oldValue = elements[index];
352
353		if (oldValue != element &&
354		(element == null || !element.equals(oldValue))) {
355	<	E[] newElements = clone(elements, len);
355	>	Object[] newElements = clone(elements, len);
356		newElements[index] = element;
357		setArray(newElements);
358		}
359	<	return oldValue;
359	>	return (E)oldValue;
360		}
361
362		/**
#	Line 369 | Line 366 | public class CopyOnWriteArrayList<E>
366		* @return <tt>true</tt> (as per the spec for {@link Collection#add})
367		*/
368		public synchronized boolean add(E e) {
369	<	E[] elements = getArray();
369	>	Object[] elements = getArray();
370		int len = elements.length;
371	<	E[] newElements = clone(elements, len + 1);
371	>	Object[] newElements = clone(elements, len + 1);
372		newElements[len] = e;
373		setArray(newElements);
374		return true;
#	Line 385 | Line 382 | public class CopyOnWriteArrayList<E>
382		* @throws IndexOutOfBoundsException {@inheritDoc}
383		*/
384		public synchronized void add(int index, E element) {
385	<	E[] elements = getArray();
385	>	Object[] elements = getArray();
386		int len = elements.length;
387		if (index > len || index < 0)
388		throw new IndexOutOfBoundsException("Index: " + index+
389		", Size: " + len);
390	<	E[] newElements;
390	>	Object[] newElements;
391		int numMoved = len - index;
392	<	if (numMoved == 0)
392	>	if (numMoved == 0)
393		newElements = clone(elements, len + 1);
394		else {
395	<	newElements = (E[]) new Object[len + 1];
395	>	newElements = new Object[len + 1];
396		System.arraycopy(elements, 0, newElements, 0, index);
397	<	System.arraycopy(elements, index, newElements, index + 1,
397	>	System.arraycopy(elements, index, newElements, index + 1,
398		numMoved);
399		}
400		newElements[index] = element;
#	Line 412 | Line 409 | public class CopyOnWriteArrayList<E>
409		* @throws IndexOutOfBoundsException {@inheritDoc}
410		*/
411		public synchronized E remove(int index) {
412	<	E[] elements = getArray();
412	>	Object[] elements = getArray();
413		int len = elements.length;
414	<	E oldValue = elements[index];
414	>	Object oldValue = elements[index];
415		int numMoved = len - index - 1;
416	<	if (numMoved == 0)
416	>	if (numMoved == 0)
417		setArray(clone(elements, len - 1));
418		else {
419	<	E[] newElements = (E[]) new Object[len - 1];
419	>	Object[] newElements = new Object[len - 1];
420		System.arraycopy(elements, 0, newElements, 0, index);
421	<	System.arraycopy(elements, index + 1, newElements, index,
421	>	System.arraycopy(elements, index + 1, newElements, index,
422		numMoved);
423		setArray(newElements);
424		}
425	<	return oldValue;
425	>	return (E)oldValue;
426		}
427
428		/**
#	Line 442 | Line 439 | public class CopyOnWriteArrayList<E>
439		* @return <tt>true</tt> if this list contained the specified element
440		*/
441		public synchronized boolean remove(Object o) {
442	<	E[] elements = getArray();
442	>	Object[] elements = getArray();
443		int len = elements.length;
444		if (len != 0) {
445		// Copy while searching for element to remove
446		// This wins in the normal case of element being present
447		int newlen = len - 1;
448	<	E[] newElements = (E[]) new Object[newlen];
449	<
448	>	Object[] newElements = new Object[newlen];
449	>
450		for (int i = 0; i < newlen; ++i) {
451	<	if (o == elements[i] ||
451	>	if (o == elements[i] ||
452		(o != null && o.equals(elements[i]))) {
453		// found one;  copy remaining and exit
454		for (int k = i + 1; k < len; ++k)
#	Line 461 | Line 458 | public class CopyOnWriteArrayList<E>
458		} else
459		newElements[i] = elements[i];
460		}
461	<
461	>
462		// special handling for last cell
463		if (o == elements[newlen] ||
464		(o != null && o.equals(elements[newlen]))) {
#	Line 469 | Line 466 | public class CopyOnWriteArrayList<E>
466		return true;
467		}
468		}
469	<	return false;
469	>	return false;
470		}
471
472		/**
#	Line 486 | Line 483 | public class CopyOnWriteArrayList<E>
483		*              &gt; size() || toIndex &lt; fromIndex)
484		*/
485		private synchronized void removeRange(int fromIndex, int toIndex) {
486	<	E[] elements = getArray();
486	>	Object[] elements = getArray();
487		int len = elements.length;
488
489		if (fromIndex < 0 || fromIndex >= len ||
#	Line 494 | Line 491 | public class CopyOnWriteArrayList<E>
491		throw new IndexOutOfBoundsException();
492		int newlen = len - (toIndex - fromIndex);
493		int numMoved = len - toIndex;
494	<	if (numMoved == 0)
494	>	if (numMoved == 0)
495		setArray(clone(elements, newlen));
496		else {
497	<	E[] newElements = (E[]) new Object[newlen];
497	>	Object[] newElements = new Object[newlen];
498		System.arraycopy(elements, 0, newElements, 0, fromIndex);
499	<	System.arraycopy(elements, toIndex, newElements,
499	>	System.arraycopy(elements, toIndex, newElements,
500		fromIndex, numMoved);
501		setArray(newElements);
502		}
#	Line 514 | Line 511 | public class CopyOnWriteArrayList<E>
511		public synchronized boolean addIfAbsent(E e) {
512		// Copy while checking if already present.
513		// This wins in the most common case where it is not present
514	<	E[] elements = getArray();
514	>	Object[] elements = getArray();
515		int len = elements.length;
516	<	E[] newElements = (E[]) new Object[len + 1];
516	>	Object[] newElements = new Object[len + 1];
517		for (int i = 0; i < len; ++i) {
518		if (e == elements[i] || (e != null && e.equals(elements[i])))
519		return false; // exit, throwing away copy
#	Line 539 | Line 536 | public class CopyOnWriteArrayList<E>
536		* @see #contains(Object)
537		*/
538		public boolean containsAll(Collection<?> c) {
539	<	E[] elements = getArray();
539	>	Object[] elements = getArray();
540		int len = elements.length;
541	<	for (Iterator e = c.iterator(); e.hasNext(); ) {
542	<	if (indexOf(e.next(), elements, 0, len) < 0)
541	>	for (Object e : c) {
542	>	if (indexOf(e, elements, 0, len) < 0)
543		return false;
544		}
545		return true;
#	Line 563 | Line 560 | public class CopyOnWriteArrayList<E>
560		* @see #remove(Object)
561		*/
562		public synchronized boolean removeAll(Collection<?> c) {
563	<	E[] elements = getArray();
563	>	Object[] elements = getArray();
564		int len = elements.length;
565		if (len != 0) {
566		// temp array holds those elements we know we want to keep
567		int newlen = 0;
568	<	E[] temp = (E[]) new Object[len];
568	>	Object[] temp = new Object[len];
569		for (int i = 0; i < len; ++i) {
570	<	E element = elements[i];
571	<	if (!c.contains(element))
570	>	Object element = elements[i];
571	>	if (!c.contains(element))
572		temp[newlen++] = element;
573		}
574		if (newlen != len) {
575	<	setArray((E[])cloneRange(temp, 0, newlen, Object[].class));
575	>	setArray(cloneRange(temp, 0, newlen, Object[].class));
576		return true;
577		}
578		}
#	Line 597 | Line 594 | public class CopyOnWriteArrayList<E>
594		* @see #remove(Object)
595		*/
596		public synchronized boolean retainAll(Collection<?> c) {
597	<	E[] elements = getArray();
597	>	Object[] elements = getArray();
598		int len = elements.length;
599		if (len != 0) {
600		int newlen = 0;
601	<	E[] temp = (E[]) new Object[len];
601	>	Object[] temp = new Object[len];
602		for (int i = 0; i < len; ++i) {
603	<	E element = elements[i];
604	<	if (c.contains(element))
603	>	Object element = elements[i];
604	>	if (c.contains(element))
605		temp[newlen++] = element;
606		}
607		if (newlen != len) {
608	<	setArray((E[])cloneRange(temp, 0, newlen, Object[].class));
608	>	setArray(cloneRange(temp, 0, newlen, Object[].class));
609		return true;
610		}
611		}
#	Line 630 | Line 627 | public class CopyOnWriteArrayList<E>
627		int added = 0;
628		int numNew = c.size();
629		if (numNew != 0) {
630	<	E[] elements = getArray();
630	>	Object[] elements = getArray();
631		int len = elements.length;
632	<
633	<	E[] temp = (E[]) new Object[numNew];
634	<	for (Iterator<? extends E> e = c.iterator(); e.hasNext(); ) {
635	<	E element = e.next();
636	<	if (indexOf(element, elements, 0, len) < 0 &&
637	<	indexOf(element, temp, 0, added) < 0)
641	<	temp[added++] = element;
632	>
633	>	Object[] temp = new Object[numNew];
634	>	for (E e : c) {
635	>	if (indexOf(e, elements, 0, len) < 0 &&
636	>	indexOf(e, temp, 0, added) < 0)
637	>	temp[added++] = e;
638		}
639		if (added != 0) {
640	<	E[] newElements = (E[]) new Object[len + added];
640	>	Object[] newElements = new Object[len + added];
641		System.arraycopy(elements, 0, newElements, 0, len);
642		System.arraycopy(temp, 0, newElements, len, added);
643		setArray(newElements);
#	Line 655 | Line 651 | public class CopyOnWriteArrayList<E>
651		* The list will be empty after this call returns.
652		*/
653		public synchronized void clear() {
654	<	setArray((E[]) new Object[0]);
654	>	setArray(new Object[0]);
655		}
656
657		/**
#	Line 670 | Line 666 | public class CopyOnWriteArrayList<E>
666		*/
667		public synchronized boolean addAll(Collection<? extends E> c) {
668		int numNew = c.size();
669	<	if (numNew == 0)
669	>	if (numNew == 0)
670		return false;
671
672	<	E[] elements = getArray();
672	>	Object[] elements = getArray();
673		int len = elements.length;
674	<	E[] newElements = (E[]) new Object[len + numNew];
674	>	Object[] newElements = new Object[len + numNew];
675		System.arraycopy(elements, 0, newElements, 0, len);
676	<	Iterator<? extends E> e = c.iterator();
677	<	for (int i = 0; i < numNew; i++)
682	<	newElements[len++] = e.next();
676	>	for (E e : c)
677	>	newElements[len++] = e;
678		setArray(newElements);
679		return true;
680		}
#	Line 701 | Line 696 | public class CopyOnWriteArrayList<E>
696		* @see #add(int,Object)
697		*/
698		public synchronized boolean addAll(int index, Collection<? extends E> c) {
699	<	E[] elements = getArray();
699	>	Object[] elements = getArray();
700		int len = elements.length;
701		if (index > len || index < 0)
702	<	throw new IndexOutOfBoundsException("Index: " + index +
702	>	throw new IndexOutOfBoundsException("Index: " + index +
703		", Size: "+ len);
704		int numNew = c.size();
705	<	if (numNew == 0)
705	>	if (numNew == 0)
706		return false;
707		int numMoved = len - index;
708	<	E[] newElements;
709	<	if (numMoved == 0)
708	>	Object[] newElements;
709	>	if (numMoved == 0)
710		newElements = clone(elements, len + numNew);
711		else {
712	<	newElements = (E[]) new Object[len + numNew];
713	<	System.arraycopy(elements, index, newElements,
712	>	newElements = new Object[len + numNew];
713	>	System.arraycopy(elements, index, newElements,
714		index + numNew, numMoved);
715	<	System.arraycopy(elements, index, newElements,
715	>	System.arraycopy(elements, index, newElements,
716		index + numNew, numMoved);
717		}
718	<	Iterator<? extends E> e = c.iterator();
719	<	for (int i = 0; i < numNew; i++)
725	<	newElements[index++] = e.next();
718	>	for (E e : c)
719	>	newElements[index++] = e;
720		setArray(newElements);
721
722		return true;
#	Line 742 | Line 736 | public class CopyOnWriteArrayList<E>
736		// Write out element count, and any hidden stuff
737		s.defaultWriteObject();
738
739	<	E[] elements = getArray();
739	>	Object[] elements = getArray();
740		int len = elements.length;
741		// Write out array length
742		s.writeInt(len);
#	Line 764 | Line 758 | public class CopyOnWriteArrayList<E>
758
759		// Read in array length and allocate array
760		int len = s.readInt();
761	<	E[] elements = (E[]) new Object[len];
761	>	Object[] elements = new Object[len];
762
763		// Read in all elements in the proper order.
764		for (int i = 0; i < len; i++)
765	<	elements[i] = (E) s.readObject();
765	>	elements[i] = s.readObject();
766		setArray(elements);
767		}
768
#	Line 777 | Line 771 | public class CopyOnWriteArrayList<E>
771		* the String representation of each element.
772		*/
773		public String toString() {
774	<	E[] elements = getArray();
774	>	Object[] elements = getArray();
775		int maxIndex = elements.length - 1;
776		StringBuffer buf = new StringBuffer();
777		buf.append("[");
#	Line 813 | Line 807 | public class CopyOnWriteArrayList<E>
807		if (size() != l2.size())
808		return false;
809
810	<	ListIterator<E> e1 = listIterator();
811	<	ListIterator<E> e2 = l2.listIterator();
810	>	ListIterator<?> e1 = listIterator();
811	>	ListIterator<?> e2 = l2.listIterator();
812		while (e1.hasNext()) {
813	<	E o1 = e1.next();
814	<	E o2 = e2.next();
813	>	Object o1 = e1.next();
814	>	Object o2 = e2.next();
815		if (!(o1 == null ? o2 == null : o1.equals(o2)))
816		return false;
817		}
#	Line 833 | Line 827 | public class CopyOnWriteArrayList<E>
827		*/
828		public int hashCode() {
829		int hashCode = 1;
830	<	E[] elements = getArray();
830	>	Object[] elements = getArray();
831		int len = elements.length;
832		for (int i = 0; i < len; ++i) {
833	<	E obj = elements[i];
833	>	Object obj = elements[i];
834		hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode());
835		}
836		return hashCode;
#	Line 878 | Line 872 | public class CopyOnWriteArrayList<E>
872		* @throws IndexOutOfBoundsException {@inheritDoc}
873		*/
874		public ListIterator<E> listIterator(final int index) {
875	<	E[] elements = getArray();
875	>	Object[] elements = getArray();
876		int len = elements.length;
877		if (index < 0 || index > len)
878		throw new IndexOutOfBoundsException("Index: " + index);
#	Line 888 | Line 882 | public class CopyOnWriteArrayList<E>
882
883		private static class COWIterator<E> implements ListIterator<E> {
884		/** Snapshot of the array **/
885	<	private final E[] snapshot;
885	>	private final Object[] snapshot;
886		/** Index of element to be returned by subsequent call to next.  */
887		private int cursor;
888
889	<	private COWIterator(E[] elements, int initialCursor) {
889	>	private COWIterator(Object[] elements, int initialCursor) {
890		cursor = initialCursor;
891		snapshot = elements;
892		}
#	Line 907 | Line 901 | public class CopyOnWriteArrayList<E>
901
902		public E next() {
903		try {
904	<	return snapshot[cursor++];
904	>	return (E)(snapshot[cursor++]);
905		} catch (IndexOutOfBoundsException ex) {
906		throw new NoSuchElementException();
907		}
#	Line 915 | Line 909 | public class CopyOnWriteArrayList<E>
909
910		public E previous() {
911		try {
912	<	return snapshot[--cursor];
912	>	return (E)(snapshot[--cursor]);
913		} catch (IndexOutOfBoundsException e) {
914		throw new NoSuchElementException();
915		}
#	Line 979 | Line 973 | public class CopyOnWriteArrayList<E>
973		*/
974		public synchronized List<E> subList(int fromIndex, int toIndex) {
975		// synchronized since sublist constructor depends on it.
976	<	E[] elements = getArray();
976	>	Object[] elements = getArray();
977		int len = elements.length;
978		if (fromIndex < 0 || toIndex > len  || fromIndex > toIndex)
979		throw new IndexOutOfBoundsException();
#	Line 1005 | Line 999 | public class CopyOnWriteArrayList<E>
999		private final CopyOnWriteArrayList<E> l;
1000		private final int offset;
1001		private int size;
1002	<	private E[] expectedArray;
1002	>	private Object[] expectedArray;
1003
1004		private COWSubList(CopyOnWriteArrayList<E> list,
1005		int fromIndex, int toIndex) {
#	Line 1106 | Line 1100 | public class CopyOnWriteArrayList<E>
1100		checkForComodification();
1101		if (fromIndex<0 || toIndex>size)
1102		throw new IndexOutOfBoundsException();
1103	<	return new COWSubList<E>(l, fromIndex + offset,
1103	>	return new COWSubList<E>(l, fromIndex + offset,
1104		toIndex + offset);
1105		}
1106		}
#	Line 1119 | Line 1113 | public class CopyOnWriteArrayList<E>
1113		private final int index;
1114		private final int offset;
1115		private final int size;
1116	<	private COWSubListIterator(List<E> l, int index, int offset,
1116	>	private COWSubListIterator(List<E> l, int index, int offset,
1117		int size) {
1118		this.index = index;
1119		this.offset = offset;
#	Line 1172 | Line 1166 | public class CopyOnWriteArrayList<E>
1166
1167		// Temporary emulations of anticipated new j.u.Arrays functions
1168
1169	<	private static <T,U> T[] cloneRange(U[] original, int from, int to,
1169	>	private static <T,U> T[] cloneRange(U[] original, int from, int to,
1170		Class<? extends T[]> newType) {
1171		int newLength = to - from;
1172		if (newLength < 0)
#	Line 1183 | Line 1177 | public class CopyOnWriteArrayList<E>
1177		Math.min(original.length - from, newLength));
1178		return copy;
1179		}
1180	<
1181	<	private static <T,U> T[] clone(U[] original, int newLength,
1180	>
1181	>	private static <T,U> T[] clone(U[] original, int newLength,
1182		Class<? extends T[]> newType) {
1183		T[] copy = (T[]) java.lang.reflect.Array.newInstance
1184		(newType.getComponentType(), newLength);

Diff Legend

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