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.139 by jsr166, Sun Jun 5 20:41:14 2016 UTC vs.
Revision 1.140 by jsr166, Tue Nov 15 22:23:57 2016 UTC

#	Line 362 | Line 362 | public class CopyOnWriteArrayList<E>
362		// Positional Access Operations
363
364		@SuppressWarnings("unchecked")
365	<	private E get(Object[] a, int index) {
365	>	static <E> E elementAt(Object[] a, int index) {
366		return (E) a[index];
367		}
368
#	Line 376 | Line 376 | public class CopyOnWriteArrayList<E>
376		* @throws IndexOutOfBoundsException {@inheritDoc}
377		*/
378		public E get(int index) {
379	<	return get(getArray(), index);
379	>	return elementAt(getArray(), index);
380		}
381
382		/**
#	Line 388 | Line 388 | public class CopyOnWriteArrayList<E>
388		public E set(int index, E element) {
389		synchronized (lock) {
390		Object[] elements = getArray();
391	<	E oldValue = get(elements, index);
391	>	E oldValue = elementAt(elements, index);
392
393		if (oldValue != element) {
394		int len = elements.length;
#	Line 459 | Line 459 | public class CopyOnWriteArrayList<E>
459		synchronized (lock) {
460		Object[] elements = getArray();
461		int len = elements.length;
462	<	E oldValue = get(elements, index);
462	>	E oldValue = elementAt(elements, index);
463		int numMoved = len - index - 1;
464		if (numMoved == 0)
465		setArray(Arrays.copyOf(elements, len - 1));
#	Line 634 | Line 634 | public class CopyOnWriteArrayList<E>
634		* @see #remove(Object)
635		*/
636		public boolean removeAll(Collection<?> c) {
637	<	if (c == null) throw new NullPointerException();
638	<	synchronized (lock) {
639	<	Object[] elements = getArray();
640	<	int len = elements.length;
641	<	if (len != 0) {
642	<	// temp array holds those elements we know we want to keep
643	<	int newlen = 0;
644	<	Object[] temp = new Object[len];
645	<	for (int i = 0; i < len; ++i) {
646	<	Object element = elements[i];
647	<	if (!c.contains(element))
648	<	temp[newlen++] = element;
649	<	}
650	<	if (newlen != len) {
651	<	setArray(Arrays.copyOf(temp, newlen));
652	<	return true;
653	<	}
654	<	}
655	<	return false;
656	<	}
637	>	Objects.requireNonNull(c);
638	>	return bulkRemove(e -> c.contains(e));
639		}
640
641		/**
#	Line 673 | Line 655 | public class CopyOnWriteArrayList<E>
655		* @see #remove(Object)
656		*/
657		public boolean retainAll(Collection<?> c) {
658	<	if (c == null) throw new NullPointerException();
659	<	synchronized (lock) {
678	<	Object[] elements = getArray();
679	<	int len = elements.length;
680	<	if (len != 0) {
681	<	// temp array holds those elements we know we want to keep
682	<	int newlen = 0;
683	<	Object[] temp = new Object[len];
684	<	for (int i = 0; i < len; ++i) {
685	<	Object element = elements[i];
686	<	if (c.contains(element))
687	<	temp[newlen++] = element;
688	<	}
689	<	if (newlen != len) {
690	<	setArray(Arrays.copyOf(temp, newlen));
691	<	return true;
692	<	}
693	<	}
694	<	return false;
695	<	}
658	>	Objects.requireNonNull(c);
659	>	return bulkRemove(e -> !c.contains(e));
660		}
661
662		/**
#	Line 821 | Line 785 | public class CopyOnWriteArrayList<E>
785
786		public boolean removeIf(Predicate<? super E> filter) {
787		if (filter == null) throw new NullPointerException();
788	+	return bulkRemove(filter);
789	+	}
790	+
791	+	// A tiny bit set implementation
792	+
793	+	private static long[] nBits(int n) {
794	+	return new long[((n - 1) >> 6) + 1];
795	+	}
796	+	private static void setBit(long[] bits, int i) {
797	+	bits[i >> 6] |= 1L << i;
798	+	}
799	+	private static boolean isClear(long[] bits, int i) {
800	+	return (bits[i >> 6] & (1L << i)) == 0;
801	+	}
802	+
803	+	private boolean bulkRemove(Predicate<? super E> filter) {
804		synchronized (lock) {
805	<	final Object[] elements = getArray();
806	<	final int len = elements.length;
807	<	int i;
808	<	for (i = 0; i < len; i++) {
809	<	@SuppressWarnings("unchecked") E e = (E) elements[i];
810	<	if (filter.test(e)) {
811	<	int newlen = i;
812	<	final Object[] newElements = new Object[len - 1];
813	<	System.arraycopy(elements, 0, newElements, 0, newlen);
814	<	for (i++; i < len; i++) {
815	<	@SuppressWarnings("unchecked") E x = (E) elements[i];
816	<	if (!filter.test(x))
817	<	newElements[newlen++] = x;
818	<	}
819	<	setArray((newlen == len - 1)
820	<	? newElements // one match => one copy
821	<	: Arrays.copyOf(newElements, newlen));
822	<	return true;
805	>	return bulkRemove(filter, 0, getArray().length);
806	>	}
807	>	}
808	>
809	>	boolean bulkRemove(Predicate<? super E> filter, int i, int end) {
810	>	// assert Thread.holdsLock(lock);
811	>	final Object[] es = getArray();
812	>	// Optimize for initial run of survivors
813	>	for (; i < end && !filter.test(elementAt(es, i)); i++)
814	>	;
815	>	if (i < end) {
816	>	final int beg = i;
817	>	final long[] deathRow = nBits(end - beg);
818	>	int deleted = 1;
819	>	deathRow[0] = 1L;   // set bit 0
820	>	for (i = beg + 1; i < end; i++)
821	>	if (filter.test(elementAt(es, i))) {
822	>	setBit(deathRow, i - beg);
823	>	deleted++;
824		}
825	<	}
826	<	return false;       // zero matches => zero copies
825	>	// Did filter reentrantly modify the list?
826	>	if (es != getArray())
827	>	throw new ConcurrentModificationException();
828	>	final Object[] newElts = Arrays.copyOf(es, es.length - deleted);
829	>	int w = beg;
830	>	for (i = beg; i < end; i++)
831	>	if (isClear(deathRow, i - beg))
832	>	newElts[w++] = es[i];
833	>	System.arraycopy(es, i, newElts, w, es.length - i);
834	>	setArray(newElts);
835	>	return true;
836	>	} else {
837	>	if (es != getArray())
838	>	throw new ConcurrentModificationException();
839	>	return false;
840		}
841		}
842
843		public void replaceAll(UnaryOperator<E> operator) {
844		if (operator == null) throw new NullPointerException();
845		synchronized (lock) {
846	<	Object[] elements = getArray();
853	<	int len = elements.length;
854	<	Object[] newElements = Arrays.copyOf(elements, len);
855	<	for (int i = 0; i < len; ++i) {
856	<	@SuppressWarnings("unchecked") E e = (E) elements[i];
857	<	newElements[i] = operator.apply(e);
858	<	}
859	<	setArray(newElements);
846	>	replaceAll(operator, 0, getArray().length);
847		}
848		}
849
850	+	void replaceAll(UnaryOperator<E> operator, int i, int end) {
851	+	// assert Thread.holdsLock(lock);
852	+	final Object[] es = getArray().clone();
853	+	for (; i < end; i++)
854	+	es[i] = operator.apply(elementAt(es, i));
855	+	setArray(es);
856	+	}
857	+
858		public void sort(Comparator<? super E> c) {
859		synchronized (lock) {
860	<	Object[] elements = getArray();
866	<	Object[] newElements = Arrays.copyOf(elements, elements.length);
867	<	@SuppressWarnings("unchecked") E[] es = (E[])newElements;
868	<	Arrays.sort(es, c);
869	<	setArray(newElements);
860	>	sort(c, 0, getArray().length);
861		}
862		}
863
864	+	@SuppressWarnings("unchecked")
865	+	void sort(Comparator<? super E> c, int i, int end) {
866	+	// assert Thread.holdsLock(lock);
867	+	final Object[] es = getArray().clone();
868	+	Arrays.sort(es, i, end, (Comparator<Object>)c);
869	+	setArray(es);
870	+	}
871	+
872		/**
873		* Saves this list to a stream (that is, serializes it).
874		*
#	Line 1149 | Line 1148 | public class CopyOnWriteArrayList<E>
1148
1149		/**
1150		* Sublist for CopyOnWriteArrayList.
1152	–	* This class extends AbstractList merely for convenience, to
1153	–	* avoid having to define addAll, etc. This doesn't hurt, but
1154	–	* is wasteful.  This class does not need or use modCount
1155	–	* mechanics in AbstractList, but does need to check for
1156	–	* concurrent modification using similar mechanics.  On each
1157	–	* operation, the array that we expect the backing list to use
1158	–	* is checked and updated.  Since we do this for all of the
1159	–	* base operations invoked by those defined in AbstractList,
1160	–	* all is well.  While inefficient, this is not worth
1161	–	* improving.  The kinds of list operations inherited from
1162	–	* AbstractList are already so slow on COW sublists that
1163	–	* adding a bit more space/time doesn't seem even noticeable.
1151		*/
1152		private static class COWSubList<E>
1153		extends AbstractList<E>
#	Line 1188 | Line 1175 | public class CopyOnWriteArrayList<E>
1175		throw new ConcurrentModificationException();
1176		}
1177
1178	+	private Object[] getArrayChecked() {
1179	+	// assert Thread.holdsLock(l.lock);
1180	+	Object[] a = l.getArray();
1181	+	if (a != expectedArray)
1182	+	throw new ConcurrentModificationException();
1183	+	return a;
1184	+	}
1185	+
1186		// only call this holding l's lock
1187		private void rangeCheck(int index) {
1188		// assert Thread.holdsLock(l.lock);
#	Line 1199 | Line 1194 | public class CopyOnWriteArrayList<E>
1194		synchronized (l.lock) {
1195		rangeCheck(index);
1196		checkForComodification();
1197	<	E x = l.set(index+offset, element);
1197	>	E x = l.set(offset + index, element);
1198		expectedArray = l.getArray();
1199		return x;
1200		}
#	Line 1209 | Line 1204 | public class CopyOnWriteArrayList<E>
1204		synchronized (l.lock) {
1205		rangeCheck(index);
1206		checkForComodification();
1207	<	return l.get(index+offset);
1207	>	return l.get(offset + index);
1208		}
1209		}
1210
#	Line 1220 | Line 1215 | public class CopyOnWriteArrayList<E>
1215		}
1216		}
1217
1218	+	public boolean add(E element) {
1219	+	synchronized (l.lock) {
1220	+	checkForComodification();
1221	+	l.add(offset + size, element);
1222	+	expectedArray = l.getArray();
1223	+	size++;
1224	+	}
1225	+	return true;
1226	+	}
1227	+
1228		public void add(int index, E element) {
1229		synchronized (l.lock) {
1230		checkForComodification();
1231		if (index < 0 || index > size)
1232		throw new IndexOutOfBoundsException
1233		(outOfBounds(index, size));
1234	<	l.add(index+offset, element);
1234	>	l.add(offset + index, element);
1235		expectedArray = l.getArray();
1236		size++;
1237		}
1238		}
1239
1240	+	public boolean addAll(Collection<? extends E> c) {
1241	+	synchronized (l.lock) {
1242	+	final Object[] oldArray = getArrayChecked();
1243	+	boolean modified = l.addAll(offset + size, c);
1244	+	size += (expectedArray = l.getArray()).length - oldArray.length;
1245	+	return modified;
1246	+	}
1247	+	}
1248	+
1249		public void clear() {
1250		synchronized (l.lock) {
1251		checkForComodification();
1252	<	l.removeRange(offset, offset+size);
1252	>	l.removeRange(offset, offset + size);
1253		expectedArray = l.getArray();
1254		size = 0;
1255		}
#	Line 1245 | Line 1259 | public class CopyOnWriteArrayList<E>
1259		synchronized (l.lock) {
1260		rangeCheck(index);
1261		checkForComodification();
1262	<	E result = l.remove(index+offset);
1262	>	E result = l.remove(offset + index);
1263		expectedArray = l.getArray();
1264		size--;
1265		return result;
#	Line 1253 | Line 1267 | public class CopyOnWriteArrayList<E>
1267		}
1268
1269		public boolean remove(Object o) {
1270	<	int index = indexOf(o);
1271	<	if (index == -1)
1272	<	return false;
1273	<	remove(index);
1274	<	return true;
1270	>	synchronized (l.lock) {
1271	>	checkForComodification();
1272	>	int index = indexOf(o);
1273	>	if (index == -1)
1274	>	return false;
1275	>	remove(index);
1276	>	return true;
1277	>	}
1278		}
1279
1280		public Iterator<E> iterator() {
#	Line 1289 | Line 1306 | public class CopyOnWriteArrayList<E>
1306
1307		public void forEach(Consumer<? super E> action) {
1308		if (action == null) throw new NullPointerException();
1309	<	int lo = offset;
1310	<	int hi = offset + size;
1311	<	Object[] a = expectedArray;
1312	<	if (l.getArray() != a)
1313	<	throw new ConcurrentModificationException();
1297	<	if (lo < 0 || hi > a.length)
1298	<	throw new IndexOutOfBoundsException();
1299	<	for (int i = lo; i < hi; ++i) {
1300	<	@SuppressWarnings("unchecked") E e = (E) a[i];
1301	<	action.accept(e);
1309	>	int i, end; final Object[] es;
1310	>	synchronized (l.lock) {
1311	>	es = getArrayChecked();
1312	>	i = offset;
1313	>	end = i + size;
1314		}
1315	+	for (; i < end; i++)
1316	+	action.accept(elementAt(es, i));
1317		}
1318
1319		public void replaceAll(UnaryOperator<E> operator) {
1320		if (operator == null) throw new NullPointerException();
1321		synchronized (l.lock) {
1322	<	int lo = offset;
1323	<	int hi = offset + size;
1324	<	Object[] elements = expectedArray;
1311	<	if (l.getArray() != elements)
1312	<	throw new ConcurrentModificationException();
1313	<	int len = elements.length;
1314	<	if (lo < 0 || hi > len)
1315	<	throw new IndexOutOfBoundsException();
1316	<	Object[] newElements = Arrays.copyOf(elements, len);
1317	<	for (int i = lo; i < hi; ++i) {
1318	<	@SuppressWarnings("unchecked") E e = (E) elements[i];
1319	<	newElements[i] = operator.apply(e);
1320	<	}
1321	<	l.setArray(expectedArray = newElements);
1322	>	checkForComodification();
1323	>	l.replaceAll(operator, offset, offset + size);
1324	>	expectedArray = l.getArray();
1325		}
1326		}
1327
1328		public void sort(Comparator<? super E> c) {
1329		synchronized (l.lock) {
1330	<	int lo = offset;
1331	<	int hi = offset + size;
1332	<	Object[] elements = expectedArray;
1330	<	if (l.getArray() != elements)
1331	<	throw new ConcurrentModificationException();
1332	<	int len = elements.length;
1333	<	if (lo < 0 || hi > len)
1334	<	throw new IndexOutOfBoundsException();
1335	<	Object[] newElements = Arrays.copyOf(elements, len);
1336	<	@SuppressWarnings("unchecked") E[] es = (E[])newElements;
1337	<	Arrays.sort(es, lo, hi, c);
1338	<	l.setArray(expectedArray = newElements);
1330	>	checkForComodification();
1331	>	l.sort(c, offset, offset + size);
1332	>	expectedArray = l.getArray();
1333		}
1334		}
1335
1336		public boolean removeAll(Collection<?> c) {
1337	<	if (c == null) throw new NullPointerException();
1338	<	boolean removed = false;
1345	<	synchronized (l.lock) {
1346	<	int n = size;
1347	<	if (n > 0) {
1348	<	int lo = offset;
1349	<	int hi = offset + n;
1350	<	Object[] elements = expectedArray;
1351	<	if (l.getArray() != elements)
1352	<	throw new ConcurrentModificationException();
1353	<	int len = elements.length;
1354	<	if (lo < 0 || hi > len)
1355	<	throw new IndexOutOfBoundsException();
1356	<	int newSize = 0;
1357	<	Object[] temp = new Object[n];
1358	<	for (int i = lo; i < hi; ++i) {
1359	<	Object element = elements[i];
1360	<	if (!c.contains(element))
1361	<	temp[newSize++] = element;
1362	<	}
1363	<	if (newSize != n) {
1364	<	Object[] newElements = new Object[len - n + newSize];
1365	<	System.arraycopy(elements, 0, newElements, 0, lo);
1366	<	System.arraycopy(temp, 0, newElements, lo, newSize);
1367	<	System.arraycopy(elements, hi, newElements,
1368	<	lo + newSize, len - hi);
1369	<	size = newSize;
1370	<	removed = true;
1371	<	l.setArray(expectedArray = newElements);
1372	<	}
1373	<	}
1374	<	}
1375	<	return removed;
1337	>	Objects.requireNonNull(c);
1338	>	return bulkRemove(e -> c.contains(e));
1339		}
1340
1341		public boolean retainAll(Collection<?> c) {
1342	<	if (c == null) throw new NullPointerException();
1343	<	boolean removed = false;
1381	<	synchronized (l.lock) {
1382	<	int n = size;
1383	<	if (n > 0) {
1384	<	int lo = offset;
1385	<	int hi = offset + n;
1386	<	Object[] elements = expectedArray;
1387	<	if (l.getArray() != elements)
1388	<	throw new ConcurrentModificationException();
1389	<	int len = elements.length;
1390	<	if (lo < 0 || hi > len)
1391	<	throw new IndexOutOfBoundsException();
1392	<	int newSize = 0;
1393	<	Object[] temp = new Object[n];
1394	<	for (int i = lo; i < hi; ++i) {
1395	<	Object element = elements[i];
1396	<	if (c.contains(element))
1397	<	temp[newSize++] = element;
1398	<	}
1399	<	if (newSize != n) {
1400	<	Object[] newElements = new Object[len - n + newSize];
1401	<	System.arraycopy(elements, 0, newElements, 0, lo);
1402	<	System.arraycopy(temp, 0, newElements, lo, newSize);
1403	<	System.arraycopy(elements, hi, newElements,
1404	<	lo + newSize, len - hi);
1405	<	size = newSize;
1406	<	removed = true;
1407	<	l.setArray(expectedArray = newElements);
1408	<	}
1409	<	}
1410	<	}
1411	<	return removed;
1342	>	Objects.requireNonNull(c);
1343	>	return bulkRemove(e -> !c.contains(e));
1344		}
1345
1346		public boolean removeIf(Predicate<? super E> filter) {
1347	<	if (filter == null) throw new NullPointerException();
1348	<	boolean removed = false;
1347	>	Objects.requireNonNull(filter);
1348	>	return bulkRemove(filter);
1349	>	}
1350	>
1351	>	private boolean bulkRemove(Predicate<? super E> filter) {
1352		synchronized (l.lock) {
1353	<	int n = size;
1354	<	if (n > 0) {
1355	<	int lo = offset;
1356	<	int hi = offset + n;
1422	<	Object[] elements = expectedArray;
1423	<	if (l.getArray() != elements)
1424	<	throw new ConcurrentModificationException();
1425	<	int len = elements.length;
1426	<	if (lo < 0 || hi > len)
1427	<	throw new IndexOutOfBoundsException();
1428	<	int newSize = 0;
1429	<	Object[] temp = new Object[n];
1430	<	for (int i = lo; i < hi; ++i) {
1431	<	@SuppressWarnings("unchecked") E e = (E) elements[i];
1432	<	if (!filter.test(e))
1433	<	temp[newSize++] = e;
1434	<	}
1435	<	if (newSize != n) {
1436	<	Object[] newElements = new Object[len - n + newSize];
1437	<	System.arraycopy(elements, 0, newElements, 0, lo);
1438	<	System.arraycopy(temp, 0, newElements, lo, newSize);
1439	<	System.arraycopy(elements, hi, newElements,
1440	<	lo + newSize, len - hi);
1441	<	size = newSize;
1442	<	removed = true;
1443	<	l.setArray(expectedArray = newElements);
1444	<	}
1445	<	}
1353	>	final Object[] oldArray = getArrayChecked();
1354	>	boolean modified = l.bulkRemove(filter, offset, offset + size);
1355	>	size += (expectedArray = l.getArray()).length - oldArray.length;
1356	>	return modified;
1357		}
1447	–	return removed;
1358		}
1359
1360		public Spliterator<E> spliterator() {
1361	<	int lo = offset;
1362	<	int hi = offset + size;
1363	<	Object[] a = expectedArray;
1364	<	if (l.getArray() != a)
1365	<	throw new ConcurrentModificationException();
1456	<	if (lo < 0 || hi > a.length)
1457	<	throw new IndexOutOfBoundsException();
1458	<	return Spliterators.spliterator
1459	<	(a, lo, hi, Spliterator.IMMUTABLE | Spliterator.ORDERED);
1361	>	synchronized (l.lock) {
1362	>	return Spliterators.spliterator(
1363	>	getArrayChecked(), offset, offset + size,
1364	>	Spliterator.IMMUTABLE | Spliterator.ORDERED);
1365	>	}
1366		}
1367
1368		}

Diff Legend

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