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.39 by dl, Sun May 29 14:02:53 2005 UTC vs.
Revision 1.40 by dl, Tue May 31 13:56:31 2005 UTC

#	Line 48 | Line 48 | import java.util.*;
48		* @param <E> the type of elements held in this collection
49		*/
50		public class CopyOnWriteArrayList<E>
51	<	implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
51	>	implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
52		private static final long serialVersionUID = 8673264195747942595L;
53
54	<	/**
55	<	* The held array. Directly accessed only within synchronized
56	<	* methods.
57	<	*/
54	>	/** The array, accessed only via getArray/setArray. */
55		private volatile transient E[] array;
56
57	<	/**
58	<	* Accessor to the array intended to be called from
62	<	* within unsynchronized read-only methods
63	<	*/
64	<	private E[] array() { return array; }
57	>	private E[]  getArray()      { return array; }
58	>	private void setArray(E[] a) { array = a; }
59
60		/**
61		* Creates an empty list.
62		*/
63		public CopyOnWriteArrayList() {
64	<	array = (E[]) new Object[0];
64	>	setArray((E[]) new Object[0]);
65		}
66
67		/**
#	Line 79 | Line 73 | public class CopyOnWriteArrayList<E>
73		* @throws NullPointerException if the specified collection is null
74		*/
75		public CopyOnWriteArrayList(Collection<? extends E> c) {
76	<	array = (E[]) new Object[c.size()];
83	<	Iterator<? extends E> i = c.iterator();
76	>	E[] elements = (E[]) new Object[c.size()];
77		int size = 0;
78	<	while (i.hasNext())
79	<	array[size++] = i.next();
78	>	for (Iterator<? extends E> i = c.iterator(); i.hasNext(); )
79	>	elements[size++] = i.next();
80	>	setArray(elements);
81		}
82
83		/**
#	Line 110 | Line 104 | public class CopyOnWriteArrayList<E>
104		* the list.
105		*/
106		private synchronized void copyIn(E[] toCopyIn, int first, int n) {
107	<	array = (E[]) new Object[n];
108	<	System.arraycopy(toCopyIn, first, array, 0, n);
107	>	int limit = first + n;
108	>	if (limit > toCopyIn.length)
109	>	throw new IndexOutOfBoundsException();
110	>	setArray((E[]) cloneRange(toCopyIn, first, limit, Object[].class));
111		}
112
113		/**
#	Line 120 | Line 116 | public class CopyOnWriteArrayList<E>
116		* @return the number of elements in this list
117		*/
118		public int size() {
119	<	return array().length;
119	>	return getArray().length;
120		}
121
122		/**
#	Line 132 | Line 128 | public class CopyOnWriteArrayList<E>
128		return size() == 0;
129		}
130
131	+	/**
132	+	* static version of indexOf, to allow repeated calls without
133	+	* needing to grab 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,
141	+	int index, int fence) {
142	+	if (o == null) {
143	+	for (int i = index; i < fence; i++)
144	+	if (elements[i] == null)
145	+	return i;
146	+	} else {
147	+	for (int i = index; i < fence; i++)
148	+	if (o.equals(elements[i]))
149	+	return i;
150	+	}
151	+	return -1;
152	+	}
153	+
154	+	/**
155	+	* static version of lastIndexOf.
156	+	* @param o element to search for
157	+	* @param elements the array
158	+	* @param index first index to search
159	+	* @return index of element, or -1 if absent
160	+	*/
161	+	private static int lastIndexOf(Object o, Object[] elements, int index) {
162	+	if (o == null) {
163	+	for (int i = index; i >= 0; i--)
164	+	if (elements[i] == null)
165	+	return i;
166	+	} else {
167	+	for (int i = index; i >= 0; i--)
168	+	if (o.equals(elements[i]))
169	+	return i;
170	+	}
171	+	return -1;
172	+	}
173	+
174		/**
175		* Returns <tt>true</tt> if this list contains the specified element.
176		* More formally, returns <tt>true</tt> if and only if this list contains
#	Line 142 | 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[] elementData = array();
185	<	int len = elementData.length;
147	<	return indexOf(o, elementData, len) >= 0;
184	>	E[] elements = getArray();
185	>	return indexOf(o, elements, 0, elements.length) >= 0;
186		}
187
188		/**
189		* {@inheritDoc}
190		*/
191		public int indexOf(Object o) {
192	<	E[] elementData = array();
193	<	int len = elementData.length;
156	<	return indexOf(o, elementData, len);
192	>	E[] elements = getArray();
193	>	return indexOf(o, elements, 0, elements.length);
194		}
195
159	–	/**
160	–	* static version allows repeated call without needing
161	–	* to grab lock for array each time
162	–	*/
163	–	private static int indexOf(Object o, Object[] elementData, int len) {
164	–	if (o == null) {
165	–	for (int i = 0; i < len; i++)
166	–	if (elementData[i]==null)
167	–	return i;
168	–	} else {
169	–	for (int i = 0; i < len; i++)
170	–	if (o.equals(elementData[i]))
171	–	return i;
172	–	}
173	–	return -1;
174	–	}
196
197		/**
198		* Returns the index of the first occurrence of the specified element in
#	Line 189 | 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[] elementData = array();
214	<	int elementCount = elementData.length;
194	<
195	<	if (e == null) {
196	<	for (int i = index ; i < elementCount ; i++)
197	<	if (elementData[i]==null)
198	<	return i;
199	<	} else {
200	<	for (int i = index ; i < elementCount ; i++)
201	<	if (e.equals(elementData[i]))
202	<	return i;
203	<	}
204	<	return -1;
213	>	E[] elements = getArray();
214	>	return indexOf(e, elements, index, elements.length);
215		}
216
217		/**
218		* {@inheritDoc}
219		*/
220		public int lastIndexOf(Object o) {
221	<	E[] elementData = array();
222	<	int len = elementData.length;
213	<	return lastIndexOf(o, elementData, len);
214	<	}
215	<
216	<	private static int lastIndexOf(Object o, Object[] elementData, int len) {
217	<	if (o == null) {
218	<	for (int i = len-1; i >= 0; i--)
219	<	if (elementData[i]==null)
220	<	return i;
221	<	} else {
222	<	for (int i = len-1; i >= 0; i--)
223	<	if (o.equals(elementData[i]))
224	<	return i;
225	<	}
226	<	return -1;
221	>	E[] elements = getArray();
222	>	return lastIndexOf(o, elements, elements.length - 1);
223		}
224
225		/**
#	Line 243 | 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	<	// needed in order to compile on 1.2b3
243	<	E[] elementData = array();
248	<	if (e == null) {
249	<	for (int i = index; i >= 0; i--)
250	<	if (elementData[i]==null)
251	<	return i;
252	<	} else {
253	<	for (int i = index; i >= 0; i--)
254	<	if (e.equals(elementData[i]))
255	<	return i;
256	<	}
257	<	return -1;
242	>	E[] elements = getArray();
243	>	return lastIndexOf(e, elements, index);
244		}
245
246		/**
#	Line 265 | Line 251 | public class CopyOnWriteArrayList<E>
251		*/
252		public Object clone() {
253		try {
254	<	E[] elementData = array();
254	>	E[] elements = getArray();
255		CopyOnWriteArrayList<E> v = (CopyOnWriteArrayList<E>)super.clone();
256	<	v.array = (E[]) new Object[elementData.length];
271	<	System.arraycopy(elementData, 0, v.array, 0, elementData.length);
256	>	v.setArray(clone(elements, elements.length));
257		return v;
258		} catch (CloneNotSupportedException e) {
259		// this shouldn't happen, since we are Cloneable
#	Line 290 | Line 275 | public class CopyOnWriteArrayList<E>
275		* @return an array containing all the elements in this list
276		*/
277		public Object[] toArray() {
278	<	Object[] elementData = array();
279	<	Object[] result = new Object[elementData.length];
295	<	System.arraycopy(elementData, 0, result, 0, elementData.length);
296	<	return result;
278	>	Object[] elements = getArray();
279	>	return clone(elements, elements.length);
280		}
281
282		/**
#	Line 336 | Line 319 | public class CopyOnWriteArrayList<E>
319		* @throws NullPointerException if the specified array is null
320		*/
321		public <T> T[] toArray(T a[]) {
322	<	E[] elementData = array();
323	<
324	<	if (a.length < elementData.length)
325	<	a = (T[])
326	<	java.lang.reflect.Array.newInstance(a.getClass().getComponentType(),
327	<	elementData.length);
328	<
329	<	System.arraycopy(elementData, 0, a, 0, elementData.length);
330	<
331	<	if (a.length > elementData.length)
349	<	a[elementData.length] = null;
350	<
351	<	return a;
322	>	E[] elements = getArray();
323	>	int len = elements.length;
324	>	if (a.length < len)
325	>	return (T[]) clone(elements, len, a.getClass());
326	>	else {
327	>	System.arraycopy(elements, 0, a, 0, len);
328	>	if (a.length > len)
329	>	a[len] = null;
330	>	return a;
331	>	}
332		}
333
334		// Positional Access Operations
#	Line 359 | Line 339 | public class CopyOnWriteArrayList<E>
339		* @throws IndexOutOfBoundsException {@inheritDoc}
340		*/
341		public E get(int index) {
342	<	return array()[index];
342	>	return getArray()[index];
343		}
344
345		/**
#	Line 369 | Line 349 | public class CopyOnWriteArrayList<E>
349		* @throws IndexOutOfBoundsException {@inheritDoc}
350		*/
351		public synchronized E set(int index, E element) {
352	<	int len = array.length;
353	<	E oldValue = array[index];
354	<
355	<	boolean same = (oldValue == element ||
356	<	(element != null && element.equals(oldValue)));
357	<	if (!same) {
358	<	E[] newArray = (E[]) new Object[len];
359	<	System.arraycopy(array, 0, newArray, 0, len);
360	<	newArray[index] = element;
381	<	array = newArray;
352	>	E[] elements = getArray();
353	>	int len = elements.length;
354	>	E oldValue = elements[index];
355	>
356	>	if (oldValue != element &&
357	>	(element == null || !element.equals(oldValue))) {
358	>	E[] newElements = clone(elements, len);
359	>	newElements[index] = element;
360	>	setArray(newElements);
361		}
362		return oldValue;
363		}
#	Line 386 | Line 365 | public class CopyOnWriteArrayList<E>
365		/**
366		* Appends the specified element to the end of this list.
367		*
368	<	* @param element element to be appended to this list
368	>	* @param e element to be appended to this list
369		* @return <tt>true</tt> (as per the spec for {@link Collection#add})
370		*/
371	<	public synchronized boolean add(E element) {
372	<	int len = array.length;
373	<	E[] newArray = (E[]) new Object[len+1];
374	<	System.arraycopy(array, 0, newArray, 0, len);
375	<	newArray[len] = element;
376	<	array = newArray;
371	>	public synchronized boolean add(E e) {
372	>	E[] elements = getArray();
373	>	int len = elements.length;
374	>	E[] newElements = clone(elements, len + 1);
375	>	newElements[len] = e;
376	>	setArray(newElements);
377		return true;
378		}
379
#	Line 406 | Line 385 | public class CopyOnWriteArrayList<E>
385		* @throws IndexOutOfBoundsException {@inheritDoc}
386		*/
387		public synchronized void add(int index, E element) {
388	<	int len = array.length;
388	>	E[] elements = getArray();
389	>	int len = elements.length;
390		if (index > len || index < 0)
391	<	throw new IndexOutOfBoundsException("Index: "+index+", Size: "+len);
392	<
393	<	E[] newArray = (E[]) new Object[len+1];
394	<	System.arraycopy(array, 0, newArray, 0, index);
395	<	newArray[index] = element;
396	<	System.arraycopy(array, index, newArray, index+1, len - index);
397	<	array = newArray;
391	>	throw new IndexOutOfBoundsException("Index: " + index+
392	>	", Size: " + len);
393	>	E[] newElements;
394	>	int numMoved = len - index;
395	>	if (numMoved == 0)
396	>	newElements = clone(elements, len + 1);
397	>	else {
398	>	newElements = (E[]) new Object[len + 1];
399	>	System.arraycopy(elements, 0, newElements, 0, index);
400	>	System.arraycopy(elements, index, newElements, index + 1,
401	>	numMoved);
402	>	}
403	>	newElements[index] = element;
404	>	setArray(newElements);
405		}
406
407		/**
#	Line 425 | Line 412 | public class CopyOnWriteArrayList<E>
412		* @throws IndexOutOfBoundsException {@inheritDoc}
413		*/
414		public synchronized E remove(int index) {
415	<	int len = array.length;
416	<	E oldValue = array[index];
417	<	E[] newArray = (E[]) new Object[len-1];
431	<	System.arraycopy(array, 0, newArray, 0, index);
415	>	E[] elements = getArray();
416	>	int len = elements.length;
417	>	E oldValue = elements[index];
418		int numMoved = len - index - 1;
419	<	if (numMoved > 0)
420	<	System.arraycopy(array, index+1, newArray, index, numMoved);
421	<	array = newArray;
419	>	if (numMoved == 0)
420	>	setArray(clone(elements, len - 1));
421	>	else {
422	>	E[] newElements = (E[]) new Object[len - 1];
423	>	System.arraycopy(elements, 0, newElements, 0, index);
424	>	System.arraycopy(elements, index + 1, newElements, index,
425	>	numMoved);
426	>	setArray(newElements);
427	>	}
428		return oldValue;
429		}
430
#	Line 450 | Line 442 | public class CopyOnWriteArrayList<E>
442		* @return <tt>true</tt> if this list contained the specified element
443		*/
444		public synchronized boolean remove(Object o) {
445	<	int len = array.length;
446	<	if (len == 0) return false;
447	<
448	<	// Copy while searching for element to remove
449	<	// This wins in the normal case of element being present
450	<
451	<	int newlen = len-1;
452	<	E[] newArray = (E[]) new Object[newlen];
453	<
454	<	for (int i = 0; i < newlen; ++i) {
455	<	if (o == array[i] ||
456	<	(o != null && o.equals(array[i]))) {
457	<	// found one;  copy remaining and exit
458	<	for (int k = i + 1; k < len; ++k) newArray[k-1] = array[k];
459	<	array = newArray;
445	>	E[] elements = getArray();
446	>	int len = elements.length;
447	>	if (len != 0) {
448	>	// Copy while searching for element to remove
449	>	// This wins in the normal case of element being present
450	>	int newlen = len - 1;
451	>	E[] newElements = (E[]) new Object[newlen];
452	>
453	>	for (int i = 0; i < newlen; ++i) {
454	>	if (o == elements[i] ||
455	>	(o != null && o.equals(elements[i]))) {
456	>	// found one;  copy remaining and exit
457	>	for (int k = i + 1; k < len; ++k)
458	>	newElements[k - 1] = elements[k];
459	>	setArray(newElements);
460	>	return true;
461	>	} else
462	>	newElements[i] = elements[i];
463	>	}
464	>
465	>	// special handling for last cell
466	>	if (o == elements[newlen] ||
467	>	(o != null && o.equals(elements[newlen]))) {
468	>	setArray(newElements);
469		return true;
470	<	} else
470	<	newArray[i] = array[i];
470	>	}
471		}
472	<	// special handling for last cell
473	<
474	<	if (o == array[newlen] ||
475	<	(o != null && o.equals(array[newlen]))) {
476	<	array = newArray;
477	<	return true;
478	<	} else
479	<	return false; // throw away copy
472	>	return false;
473		}
474
475		/**
#	Line 493 | Line 486 | public class CopyOnWriteArrayList<E>
486		*              &gt; size() || toIndex &lt; fromIndex)
487		*/
488		private synchronized void removeRange(int fromIndex, int toIndex) {
489	<	int len = array.length;
489	>	E[] elements = getArray();
490	>	int len = elements.length;
491
492		if (fromIndex < 0 || fromIndex >= len ||
493	<	toIndex > len || toIndex < fromIndex)
493	>	toIndex > len || toIndex < fromIndex)
494		throw new IndexOutOfBoundsException();
495	<
495	>	int newlen = len - (toIndex - fromIndex);
496		int numMoved = len - toIndex;
497	<	int newlen = len - (toIndex-fromIndex);
498	<	E[] newArray = (E[]) new Object[newlen];
499	<	System.arraycopy(array, 0, newArray, 0, fromIndex);
500	<	System.arraycopy(array, toIndex, newArray, fromIndex, numMoved);
501	<	array = newArray;
497	>	if (numMoved == 0)
498	>	setArray(clone(elements, newlen));
499	>	else {
500	>	E[] newElements = (E[]) new Object[newlen];
501	>	System.arraycopy(elements, 0, newElements, 0, fromIndex);
502	>	System.arraycopy(elements, toIndex, newElements,
503	>	fromIndex, numMoved);
504	>	setArray(newElements);
505	>	}
506		}
507
508		/**
509		* Append the element if not present.
510		*
511	<	* @param element element to be added to this list, if absent
511	>	* @param e element to be added to this list, if absent
512		* @return <tt>true</tt> if the element was added
513		*/
514	<	public synchronized boolean addIfAbsent(E element) {
514	>	public synchronized boolean addIfAbsent(E e) {
515		// Copy while checking if already present.
516		// This wins in the most common case where it is not present
517	<	int len = array.length;
518	<	E[] newArray = (E[]) new Object[len + 1];
517	>	E[] elements = getArray();
518	>	int len = elements.length;
519	>	E[] newElements = (E[]) new Object[len + 1];
520		for (int i = 0; i < len; ++i) {
521	<	if (element == array[i] ||
523	<	(element != null && element.equals(array[i])))
521	>	if (e == elements[i] || (e != null && e.equals(elements[i])))
522		return false; // exit, throwing away copy
523		else
524	<	newArray[i] = array[i];
524	>	newElements[i] = elements[i];
525		}
526	<	newArray[len] = element;
527	<	array = newArray;
526	>	newElements[len] = e;
527	>	setArray(newElements);
528		return true;
529		}
530
#	Line 541 | Line 539 | public class CopyOnWriteArrayList<E>
539		* @see #contains(Object)
540		*/
541		public boolean containsAll(Collection<?> c) {
542	<	E[] elementData = array();
543	<	int len = elementData.length;
544	<	Iterator e = c.iterator();
545	<	while (e.hasNext())
548	<	if (indexOf(e.next(), elementData, len) < 0)
542	>	E[] elements = getArray();
543	>	int len = elements.length;
544	>	for (Iterator e = c.iterator(); e.hasNext(); ) {
545	>	if (indexOf(e.next(), elements, 0, len) < 0)
546		return false;
547	<
547	>	}
548		return true;
549		}
550
#	Line 566 | Line 563 | public class CopyOnWriteArrayList<E>
563		* @see #remove(Object)
564		*/
565		public synchronized boolean removeAll(Collection<?> c) {
566	<	E[] elementData = array;
567	<	int len = elementData.length;
568	<	if (len == 0) return false;
569	<
570	<	// temp array holds those elements we know we want to keep
571	<	E[] temp = (E[]) new Object[len];
572	<	int newlen = 0;
573	<	for (int i = 0; i < len; ++i) {
574	<	E element = elementData[i];
575	<	if (!c.contains(element)) {
576	<	temp[newlen++] = element;
566	>	E[] elements = getArray();
567	>	int len = elements.length;
568	>	if (len != 0) {
569	>	// temp array holds those elements we know we want to keep
570	>	int newlen = 0;
571	>	E[] temp = (E[]) new Object[len];
572	>	for (int i = 0; i < len; ++i) {
573	>	E element = elements[i];
574	>	if (!c.contains(element))
575	>	temp[newlen++] = element;
576	>	}
577	>	if (newlen != len) {
578	>	setArray((E[])cloneRange(temp, 0, newlen, Object[].class));
579	>	return true;
580		}
581		}
582	<
583	<	if (newlen == len) return false;
584	<
585	<	//  copy temp as new array
586	<	E[] newArray = (E[]) new Object[newlen];
587	<	System.arraycopy(temp, 0, newArray, 0, newlen);
588	<	array = newArray;
589	<	return true;
582	>	return false;
583		}
584
585		/**
#	Line 604 | Line 597 | public class CopyOnWriteArrayList<E>
597		* @see #remove(Object)
598		*/
599		public synchronized boolean retainAll(Collection<?> c) {
600	<	E[] elementData = array;
601	<	int len = elementData.length;
602	<	if (len == 0) return false;
603	<
604	<	E[] temp = (E[]) new Object[len];
605	<	int newlen = 0;
606	<	for (int i = 0; i < len; ++i) {
607	<	E element = elementData[i];
608	<	if (c.contains(element)) {
609	<	temp[newlen++] = element;
600	>	E[] elements = getArray();
601	>	int len = elements.length;
602	>	if (len != 0) {
603	>	int newlen = 0;
604	>	E[] temp = (E[]) new Object[len];
605	>	for (int i = 0; i < len; ++i) {
606	>	E element = elements[i];
607	>	if (c.contains(element))
608	>	temp[newlen++] = element;
609	>	}
610	>	if (newlen != len) {
611	>	setArray((E[])cloneRange(temp, 0, newlen, Object[].class));
612	>	return true;
613		}
614		}
615	<
620	<	if (newlen == len) return false;
621	<
622	<	E[] newArray = (E[]) new Object[newlen];
623	<	System.arraycopy(temp, 0, newArray, 0, newlen);
624	<	array = newArray;
625	<	return true;
615	>	return false;
616		}
617
618		/**
#	Line 637 | Line 627 | public class CopyOnWriteArrayList<E>
627		* @see #addIfAbsent(Object)
628		*/
629		public synchronized int addAllAbsent(Collection<? extends E> c) {
640	–	int numNew = c.size();
641	–	if (numNew == 0) return 0;
642	–
643	–	E[] elementData = array;
644	–	int len = elementData.length;
645	–
646	–	E[] temp = (E[]) new Object[numNew];
630		int added = 0;
631	<	Iterator<? extends E> e = c.iterator();
632	<	while (e.hasNext()) {
633	<	E element = e.next();
634	<	if (indexOf(element, elementData, len) < 0) {
635	<	if (indexOf(element, temp, added) < 0) {
631	>	int numNew = c.size();
632	>	if (numNew != 0) {
633	>	E[] elements = getArray();
634	>	int len = elements.length;
635	>
636	>	E[] temp = (E[]) new Object[numNew];
637	>	for (Iterator<? extends E> e = c.iterator(); e.hasNext(); ) {
638	>	E element = e.next();
639	>	if (indexOf(element, elements, 0, len) < 0 &&
640	>	indexOf(element, temp, 0, added) < 0)
641		temp[added++] = element;
642	<	}
642	>	}
643	>	if (added != 0) {
644	>	E[] newElements = (E[]) new Object[len + added];
645	>	System.arraycopy(elements, 0, newElements, 0, len);
646	>	System.arraycopy(temp, 0, newElements, len, added);
647	>	setArray(newElements);
648		}
649		}
657	–
658	–	if (added == 0) return 0;
659	–
660	–	E[] newArray = (E[]) new Object[len+added];
661	–	System.arraycopy(elementData, 0, newArray, 0, len);
662	–	System.arraycopy(temp, 0, newArray, len, added);
663	–	array = newArray;
650		return added;
651		}
652
#	Line 669 | Line 655 | public class CopyOnWriteArrayList<E>
655		* The list will be empty after this call returns.
656		*/
657		public synchronized void clear() {
658	<	array = (E[]) new Object[0];
658	>	setArray((E[]) new Object[0]);
659		}
660
661		/**
#	Line 684 | Line 670 | public class CopyOnWriteArrayList<E>
670		*/
671		public synchronized boolean addAll(Collection<? extends E> c) {
672		int numNew = c.size();
673	<	if (numNew == 0) return false;
673	>	if (numNew == 0)
674	>	return false;
675
676	<	int len = array.length;
677	<	E[] newArray = (E[]) new Object[len+numNew];
678	<	System.arraycopy(array, 0, newArray, 0, len);
676	>	E[] elements = getArray();
677	>	int len = elements.length;
678	>	E[] newElements = (E[]) new Object[len + numNew];
679	>	System.arraycopy(elements, 0, newElements, 0, len);
680		Iterator<? extends E> e = c.iterator();
681	<	for (int i=0; i<numNew; i++)
682	<	newArray[len++] = e.next();
683	<	array = newArray;
696	<
681	>	for (int i = 0; i < numNew; i++)
682	>	newElements[len++] = e.next();
683	>	setArray(newElements);
684		return true;
685		}
686
#	Line 714 | Line 701 | public class CopyOnWriteArrayList<E>
701		* @see #add(int,Object)
702		*/
703		public synchronized boolean addAll(int index, Collection<? extends E> c) {
704	<	int len = array.length;
704	>	E[] elements = getArray();
705	>	int len = elements.length;
706		if (index > len || index < 0)
707	<	throw new IndexOutOfBoundsException("Index: "+index+", Size: "+len);
708	<
707	>	throw new IndexOutOfBoundsException("Index: " + index +
708	>	", Size: "+ len);
709		int numNew = c.size();
710	<	if (numNew == 0) return false;
711	<
724	<	E[] newArray = (E[]) new Object[len+numNew];
725	<	System.arraycopy(array, 0, newArray, 0, len);
710	>	if (numNew == 0)
711	>	return false;
712		int numMoved = len - index;
713	<	if (numMoved > 0)
714	<	System.arraycopy(array, index, newArray, index + numNew, numMoved);
713	>	E[] newElements;
714	>	if (numMoved == 0)
715	>	newElements = clone(elements, len + numNew);
716	>	else {
717	>	newElements = (E[]) new Object[len + numNew];
718	>	System.arraycopy(elements, index, newElements,
719	>	index + numNew, numMoved);
720	>	System.arraycopy(elements, index, newElements,
721	>	index + numNew, numMoved);
722	>	}
723		Iterator<? extends E> e = c.iterator();
724	<	for (int i=0; i<numNew; i++)
725	<	newArray[index++] = e.next();
726	<	array = newArray;
724	>	for (int i = 0; i < numNew; i++)
725	>	newElements[index++] = e.next();
726	>	setArray(newElements);
727
728		return true;
729		}
730
731		/**
738	–	* Checks if the given index is in range.  If not, throws an appropriate
739	–	* runtime exception.
740	–	*/
741	–	private void rangeCheck(int index, int length) {
742	–	if (index >= length || index < 0)
743	–	throw new IndexOutOfBoundsException("Index: "+index+", Size: "+ length);
744	–	}
745	–
746	–	/**
732		* Save the state of the list to a stream (i.e., serialize it).
733		*
734		* @serialData The length of the array backing the list is emitted
#	Line 757 | Line 742 | public class CopyOnWriteArrayList<E>
742		// Write out element count, and any hidden stuff
743		s.defaultWriteObject();
744
745	<	E[] elementData = array();
745	>	E[] elements = getArray();
746	>	int len = elements.length;
747		// Write out array length
748	<	s.writeInt(elementData.length);
748	>	s.writeInt(len);
749
750		// Write out all elements in the proper order.
751	<	for (int i=0; i<elementData.length; i++)
752	<	s.writeObject(elementData[i]);
751	>	for (int i = 0; i < len; i++)
752	>	s.writeObject(elements[i]);
753		}
754
755		/**
#	Line 777 | Line 763 | public class CopyOnWriteArrayList<E>
763		s.defaultReadObject();
764
765		// Read in array length and allocate array
766	<	int arrayLength = s.readInt();
767	<	E[] elementData = (E[]) new Object[arrayLength];
766	>	int len = s.readInt();
767	>	E[] elements = (E[]) new Object[len];
768
769		// Read in all elements in the proper order.
770	<	for (int i=0; i<elementData.length; i++)
771	<	elementData[i] = (E) s.readObject();
772	<	array = elementData;
770	>	for (int i = 0; i < len; i++)
771	>	elements[i] = (E) s.readObject();
772	>	setArray(elements);
773		}
774
775		/**
#	Line 791 | Line 777 | public class CopyOnWriteArrayList<E>
777		* the String representation of each element.
778		*/
779		public String toString() {
780	+	E[] elements = getArray();
781	+	int maxIndex = elements.length - 1;
782		StringBuffer buf = new StringBuffer();
795	–	Iterator e = iterator();
783		buf.append("[");
797	–	int maxIndex = size() - 1;
784		for (int i = 0; i <= maxIndex; i++) {
785	<	buf.append(String.valueOf(e.next()));
785	>	buf.append(String.valueOf(elements[i]));
786		if (i < maxIndex)
787		buf.append(", ");
788		}
#	Line 832 | Line 818 | public class CopyOnWriteArrayList<E>
818		while (e1.hasNext()) {
819		E o1 = e1.next();
820		E o2 = e2.next();
821	<	if (!(o1==null ? o2==null : o1.equals(o2)))
821	>	if (!(o1 == null ? o2 == null : o1.equals(o2)))
822		return false;
823		}
824		return true;
#	Line 847 | Line 833 | public class CopyOnWriteArrayList<E>
833		*/
834		public int hashCode() {
835		int hashCode = 1;
836	<	Iterator<E> i = iterator();
837	<	while (i.hasNext()) {
838	<	E obj = i.next();
839	<	hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
836	>	E[] elements = getArray();
837	>	int len = elements.length;
838	>	for (int i = 0; i < len; ++i) {
839	>	E obj = elements[i];
840	>	hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode());
841		}
842		return hashCode;
843		}
#	Line 866 | Line 853 | public class CopyOnWriteArrayList<E>
853		* @return an iterator over the elements in this list in proper sequence
854		*/
855		public Iterator<E> iterator() {
856	<	return new COWIterator<E>(array(), 0);
856	>	return new COWIterator<E>(getArray(), 0);
857		}
858
859		/**
#	Line 878 | Line 865 | public class CopyOnWriteArrayList<E>
865		* <tt>remove</tt>, <tt>set</tt> or <tt>add</tt> methods.
866		*/
867		public ListIterator<E> listIterator() {
868	<	return new COWIterator<E>(array(), 0);
868	>	return new COWIterator<E>(getArray(), 0);
869		}
870
871		/**
#	Line 891 | Line 878 | public class CopyOnWriteArrayList<E>
878		* @throws IndexOutOfBoundsException {@inheritDoc}
879		*/
880		public ListIterator<E> listIterator(final int index) {
881	<	E[] elementData = array();
882	<	int len = elementData.length;
883	<	if (index<0 || index>len)
884	<	throw new IndexOutOfBoundsException("Index: "+index);
881	>	E[] elements = getArray();
882	>	int len = elements.length;
883	>	if (index < 0 || index > len)
884	>	throw new IndexOutOfBoundsException("Index: " + index);
885
886	<	return new COWIterator<E>(array(), index);
886	>	return new COWIterator<E>(getArray(), index);
887		}
888
889		private static class COWIterator<E> implements ListIterator<E> {
903	–
890		/** Snapshot of the array **/
891	<	private final E[] array;
892	<
907	<	/**
908	<	* Index of element to be returned by subsequent call to next.
909	<	*/
891	>	private final E[] snapshot;
892	>	/** Index of element to be returned by subsequent call to next.  */
893		private int cursor;
894
895	<	private COWIterator(E[] elementArray, int initialCursor) {
913	<	array = elementArray;
895	>	private COWIterator(E[] elements, int initialCursor) {
896		cursor = initialCursor;
897	+	snapshot = elements;
898		}
899
900		public boolean hasNext() {
901	<	return cursor < array.length;
901	>	return cursor < snapshot.length;
902		}
903
904		public boolean hasPrevious() {
#	Line 924 | Line 907 | public class CopyOnWriteArrayList<E>
907
908		public E next() {
909		try {
910	<	return array[cursor++];
910	>	return snapshot[cursor++];
911		} catch (IndexOutOfBoundsException ex) {
912		throw new NoSuchElementException();
913		}
#	Line 932 | Line 915 | public class CopyOnWriteArrayList<E>
915
916		public E previous() {
917		try {
918	<	return array[--cursor];
918	>	return snapshot[--cursor];
919		} catch (IndexOutOfBoundsException e) {
920		throw new NoSuchElementException();
921		}
#	Line 943 | Line 926 | public class CopyOnWriteArrayList<E>
926		}
927
928		public int previousIndex() {
929	<	return cursor-1;
929	>	return cursor - 1;
930		}
931
932		/**
#	Line 975 | Line 958 | public class CopyOnWriteArrayList<E>
958		}
959
960		/**
961	<	* Returns a view of the portion of this list between <tt>fromIndex</tt>,
962	<	* inclusive, and <tt>toIndex</tt>, exclusive.  The returned list is
963	<	* backed by this list, so changes in the returned list are reflected in
964	<	* this list, and vice-versa.  While mutative operations are supported,
965	<	* they are probably not very useful for CopyOnWriteArrayLists.
966	<	*
967	<	* <p>The semantics of the list returned by this method become undefined if
968	<	* the backing list (i.e., this list) is <i>structurally modified</i> in
969	<	* any way other than via the returned list.  (Structural modifications are
970	<	* those that change the size of the list, or otherwise perturb it in such
971	<	* a fashion that iterations in progress may yield incorrect results.)
961	>	* Returns a view of the portion of this list between
962	>	* <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
963	>	* The returned list is backed by this list, so changes in the
964	>	* returned list are reflected in this list, and vice-versa.
965	>	* While mutative operations are supported, they are probably not
966	>	* very useful for CopyOnWriteArrayLists.
967	>	*
968	>	* <p>The semantics of the list returned by this method become
969	>	* undefined if the backing list (i.e., this list) is
970	>	* <i>structurally modified</i> in any way other than via the
971	>	* returned list.  (Structural modifications are those that change
972	>	* the size of the list, or otherwise perturb it in such a fashion
973	>	* that iterations in progress may yield incorrect results.)
974		*
975		* @param fromIndex low endpoint (inclusive) of the subList
976		* @param toIndex high endpoint (exclusive) of the subList
#	Line 994 | Line 979 | public class CopyOnWriteArrayList<E>
979		*/
980		public synchronized List<E> subList(int fromIndex, int toIndex) {
981		// synchronized since sublist constructor depends on it.
982	<	int len = array.length;
983	<	if (fromIndex<0 || toIndex>len  || fromIndex>toIndex)
982	>	E[] elements = getArray();
983	>	int len = elements.length;
984	>	if (fromIndex < 0 || toIndex > len  || fromIndex > toIndex)
985		throw new IndexOutOfBoundsException();
986		return new COWSubList<E>(this, fromIndex, toIndex);
987		}
988
989		private static class COWSubList<E> extends AbstractList<E> {
1004	–
990		/*
991		This class extends AbstractList merely for convenience, to
992		avoid having to define addAll, etc. This doesn't hurt, but
#	Line 1015 | Line 1000 | public class CopyOnWriteArrayList<E>
1000		improving.  The kinds of list operations inherited from
1001		AbstractList are already so slow on COW sublists that
1002		adding a bit more space/time doesn't seem even noticeable.
1003	<	*/
1003	>	*/
1004
1005		private final CopyOnWriteArrayList<E> l;
1006		private final int offset;
#	Line 1023 | Line 1008 | public class CopyOnWriteArrayList<E>
1008		private E[] expectedArray;
1009
1010		private COWSubList(CopyOnWriteArrayList<E> list,
1011	<	int fromIndex, int toIndex) {
1011	>	int fromIndex, int toIndex) {
1012		l = list;
1013	<	expectedArray = l.array();
1013	>	expectedArray = l.getArray();
1014		offset = fromIndex;
1015		size = toIndex - fromIndex;
1016		}
1017
1018		// only call this holding l's lock
1019		private void checkForComodification() {
1020	<	if (l.array != expectedArray)
1020	>	if (l.getArray() != expectedArray)
1021		throw new ConcurrentModificationException();
1022		}
1023
1024		// only call this holding l's lock
1025		private void rangeCheck(int index) {
1026	<	if (index<0 || index>=size)
1027	<	throw new IndexOutOfBoundsException("Index: "+index+ ",Size: "+size);
1026	>	if (index < 0 || index >= size)
1027	>	throw new IndexOutOfBoundsException("Index: " + index +
1028	>	",Size: " + size);
1029		}
1030
1045	–
1031		public E set(int index, E element) {
1032		synchronized(l) {
1033		rangeCheck(index);
1034		checkForComodification();
1035	<	E x = l.set(index+offset, element);
1036	<	expectedArray = l.array;
1035	>	E x = l.set(index + offset, element);
1036	>	expectedArray = l.getArray();
1037		return x;
1038		}
1039		}
#	Line 1057 | Line 1042 | public class CopyOnWriteArrayList<E>
1042		synchronized(l) {
1043		rangeCheck(index);
1044		checkForComodification();
1045	<	return l.get(index+offset);
1045	>	return l.get(index + offset);
1046		}
1047		}
1048
#	Line 1073 | Line 1058 | public class CopyOnWriteArrayList<E>
1058		checkForComodification();
1059		if (index<0 || index>size)
1060		throw new IndexOutOfBoundsException();
1061	<	l.add(index+offset, element);
1062	<	expectedArray = l.array;
1061	>	l.add(index + offset, element);
1062	>	expectedArray = l.getArray();
1063		size++;
1064		}
1065		}
#	Line 1083 | Line 1068 | public class CopyOnWriteArrayList<E>
1068		synchronized(l) {
1069		checkForComodification();
1070		l.removeRange(offset, offset+size);
1071	<	expectedArray = l.array;
1071	>	expectedArray = l.getArray();
1072		size = 0;
1073		}
1074		}
#	Line 1092 | Line 1077 | public class CopyOnWriteArrayList<E>
1077		synchronized(l) {
1078		rangeCheck(index);
1079		checkForComodification();
1080	<	E result = l.remove(index+offset);
1081	<	expectedArray = l.array;
1080	>	E result = l.remove(index + offset);
1081	>	expectedArray = l.getArray();
1082		size--;
1083		return result;
1084		}
#	Line 1110 | Line 1095 | public class CopyOnWriteArrayList<E>
1095		synchronized(l) {
1096		checkForComodification();
1097		if (index<0 || index>size)
1098	<	throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
1098	>	throw new IndexOutOfBoundsException("Index: "+index+
1099	>	", Size: "+size);
1100		return new COWSubListIterator<E>(l, index, offset, size);
1101		}
1102		}
#	Line 1120 | Line 1106 | public class CopyOnWriteArrayList<E>
1106		checkForComodification();
1107		if (fromIndex<0 || toIndex>size)
1108		throw new IndexOutOfBoundsException();
1109	<	return new COWSubList<E>(l, fromIndex+offset, toIndex+offset);
1109	>	return new COWSubList<E>(l, fromIndex + offset,
1110	>	toIndex + offset);
1111		}
1112		}
1113
#	Line 1132 | Line 1119 | public class CopyOnWriteArrayList<E>
1119		private final int index;
1120		private final int offset;
1121		private final int size;
1122	<	private COWSubListIterator(List<E> l, int index, int offset, int size) {
1122	>	private COWSubListIterator(List<E> l, int index, int offset,
1123	>	int size) {
1124		this.index = index;
1125		this.offset = offset;
1126		this.size = size;
1127	<	i = l.listIterator(index+offset);
1127	>	i = l.listIterator(index + offset);
1128		}
1129
1130		public boolean hasNext() {
#	Line 1182 | Line 1170 | public class CopyOnWriteArrayList<E>
1170		}
1171		}
1172
1173	+	// Temporary emulations of anticipated new j.u.Arrays functions
1174	+
1175	+	private static <T,U> T[] cloneRange(U[] original, int from, int to,
1176	+	Class<? extends T[]> newType) {
1177	+	int newLength = to - from;
1178	+	if (newLength < 0)
1179	+	throw new IllegalArgumentException(from + " > " + to);
1180	+	T[] copy = (T[]) java.lang.reflect.Array.newInstance
1181	+	(newType.getComponentType(), newLength);
1182	+	System.arraycopy(original, from, copy, 0,
1183	+	Math.min(original.length - from, newLength));
1184	+	return copy;
1185	+	}
1186	+
1187	+	private static <T,U> T[] clone(U[] original, int newLength,
1188	+	Class<? extends T[]> newType) {
1189	+	T[] copy = (T[]) java.lang.reflect.Array.newInstance
1190	+	(newType.getComponentType(), newLength);
1191	+	System.arraycopy(original, 0, copy, 0,
1192	+	Math.min(original.length, newLength));
1193	+	return copy;
1194	+	}
1195	+
1196	+	private static <T> T[] clone(T[] original, int newLength) {
1197	+	return (T[]) clone(original, newLength, original.getClass());
1198	+	}
1199	+
1200		}

Diff Legend

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