19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 /*
27 * Written by Doug Lea with assistance from members of JCP JSR-166
28 * Expert Group. Adapted and released, under explicit permission,
29 * from JDK ArrayList.java which carries the following copyright:
30 *
31 * Copyright 1997 by Sun Microsystems, Inc.,
32 * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
33 * All rights reserved.
34 */
35
36 package java.util.concurrent;
37 import java.util.*;
38 import java.util.concurrent.locks.ReentrantLock;
39
40 /**
41 * A thread-safe variant of {@link java.util.ArrayList} in which all mutative
42 * operations (<tt>add</tt>, <tt>set</tt>, and so on) are implemented by
43 * making a fresh copy of the underlying array.
44 *
45 * <p> This is ordinarily too costly, but may be <em>more</em> efficient
46 * than alternatives when traversal operations vastly outnumber
47 * mutations, and is useful when you cannot or don't want to
48 * synchronize traversals, yet need to preclude interference among
49 * concurrent threads. The "snapshot" style iterator method uses a
50 * reference to the state of the array at the point that the iterator
51 * was created. This array never changes during the lifetime of the
52 * iterator, so interference is impossible and the iterator is
53 * guaranteed not to throw <tt>ConcurrentModificationException</tt>.
54 * The iterator will not reflect additions, removals, or changes to
55 * the list since the iterator was created. Element-changing
56 * operations on iterators themselves (<tt>remove</tt>, <tt>set</tt>, and
57 * <tt>add</tt>) are not supported. These methods throw
58 * <tt>UnsupportedOperationException</tt>.
1243 return new COWSubListIterator<E>(l, index, offset, size);
1244 } finally {
1245 lock.unlock();
1246 }
1247 }
1248
1249 public List<E> subList(int fromIndex, int toIndex) {
1250 final ReentrantLock lock = l.lock;
1251 lock.lock();
1252 try {
1253 checkForComodification();
1254 if (fromIndex<0 || toIndex>size)
1255 throw new IndexOutOfBoundsException();
1256 return new COWSubList<E>(l, fromIndex + offset,
1257 toIndex + offset);
1258 } finally {
1259 lock.unlock();
1260 }
1261 }
1262
1263 }
1264
1265
1266 private static class COWSubListIterator<E> implements ListIterator<E> {
1267 private final ListIterator<E> it;
1268 private final int offset;
1269 private final int size;
1270
1271 COWSubListIterator(List<E> l, int index, int offset, int size) {
1272 this.offset = offset;
1273 this.size = size;
1274 it = l.listIterator(index+offset);
1275 }
1276
1277 public boolean hasNext() {
1278 return nextIndex() < size;
1279 }
1280
1281 public E next() {
1282 if (hasNext())
1283 return it.next();
1284 else
1315 public void add(E e) {
1316 throw new UnsupportedOperationException();
1317 }
1318 }
1319
1320 // Support for resetting lock while deserializing
1321 private void resetLock() {
1322 UNSAFE.putObjectVolatile(this, lockOffset, new ReentrantLock());
1323 }
1324 private static final sun.misc.Unsafe UNSAFE;
1325 private static final long lockOffset;
1326 static {
1327 try {
1328 UNSAFE = sun.misc.Unsafe.getUnsafe();
1329 Class<?> k = CopyOnWriteArrayList.class;
1330 lockOffset = UNSAFE.objectFieldOffset
1331 (k.getDeclaredField("lock"));
1332 } catch (Exception e) {
1333 throw new Error(e);
1334 }
1335 }
1336 }
|
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 /*
27 * Written by Doug Lea with assistance from members of JCP JSR-166
28 * Expert Group. Adapted and released, under explicit permission,
29 * from JDK ArrayList.java which carries the following copyright:
30 *
31 * Copyright 1997 by Sun Microsystems, Inc.,
32 * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
33 * All rights reserved.
34 */
35
36 package java.util.concurrent;
37 import java.util.*;
38 import java.util.concurrent.locks.ReentrantLock;
39 import java.util.function.Consumer;
40 import java.util.function.Predicate;
41 import java.util.function.UnaryOperator;
42
43 /**
44 * A thread-safe variant of {@link java.util.ArrayList} in which all mutative
45 * operations (<tt>add</tt>, <tt>set</tt>, and so on) are implemented by
46 * making a fresh copy of the underlying array.
47 *
48 * <p> This is ordinarily too costly, but may be <em>more</em> efficient
49 * than alternatives when traversal operations vastly outnumber
50 * mutations, and is useful when you cannot or don't want to
51 * synchronize traversals, yet need to preclude interference among
52 * concurrent threads. The "snapshot" style iterator method uses a
53 * reference to the state of the array at the point that the iterator
54 * was created. This array never changes during the lifetime of the
55 * iterator, so interference is impossible and the iterator is
56 * guaranteed not to throw <tt>ConcurrentModificationException</tt>.
57 * The iterator will not reflect additions, removals, or changes to
58 * the list since the iterator was created. Element-changing
59 * operations on iterators themselves (<tt>remove</tt>, <tt>set</tt>, and
60 * <tt>add</tt>) are not supported. These methods throw
61 * <tt>UnsupportedOperationException</tt>.
1246 return new COWSubListIterator<E>(l, index, offset, size);
1247 } finally {
1248 lock.unlock();
1249 }
1250 }
1251
1252 public List<E> subList(int fromIndex, int toIndex) {
1253 final ReentrantLock lock = l.lock;
1254 lock.lock();
1255 try {
1256 checkForComodification();
1257 if (fromIndex<0 || toIndex>size)
1258 throw new IndexOutOfBoundsException();
1259 return new COWSubList<E>(l, fromIndex + offset,
1260 toIndex + offset);
1261 } finally {
1262 lock.unlock();
1263 }
1264 }
1265
1266 @Override
1267 public void forEach(Consumer<? super E> action) {
1268 @SuppressWarnings("unchecked")
1269 final E[] elements = (E[]) l.getArray();
1270 checkForComodification();
1271 l.forEach(action, elements, offset, offset + size);
1272 }
1273
1274 @Override
1275 public void sort(Comparator<? super E> c) {
1276 final ReentrantLock lock = l.lock;
1277 lock.lock();
1278 try {
1279 checkForComodification();
1280 l.sort(c, offset, offset + size);
1281 expectedArray = l.getArray();
1282 } finally {
1283 lock.unlock();
1284 }
1285 }
1286
1287 @Override
1288 public boolean removeIf(Predicate<? super E> filter) {
1289 Objects.requireNonNull(filter);
1290 final ReentrantLock lock = l.lock;
1291 lock.lock();
1292 try {
1293 checkForComodification();
1294 final int removeCount =
1295 l.removeIf(filter, offset, offset + size);
1296 expectedArray = l.getArray();
1297 size -= removeCount;
1298 return removeCount > 0;
1299 } finally {
1300 lock.unlock();
1301 }
1302 }
1303
1304 @Override
1305 public void replaceAll(UnaryOperator<E> operator) {
1306 final ReentrantLock lock = l.lock;
1307 lock.lock();
1308 try {
1309 checkForComodification();
1310 l.replaceAll(operator, offset, offset + size);
1311 expectedArray = l.getArray();
1312 } finally {
1313 lock.unlock();
1314 }
1315 }
1316 }
1317
1318 private static class COWSubListIterator<E> implements ListIterator<E> {
1319 private final ListIterator<E> it;
1320 private final int offset;
1321 private final int size;
1322
1323 COWSubListIterator(List<E> l, int index, int offset, int size) {
1324 this.offset = offset;
1325 this.size = size;
1326 it = l.listIterator(index+offset);
1327 }
1328
1329 public boolean hasNext() {
1330 return nextIndex() < size;
1331 }
1332
1333 public E next() {
1334 if (hasNext())
1335 return it.next();
1336 else
1367 public void add(E e) {
1368 throw new UnsupportedOperationException();
1369 }
1370 }
1371
1372 // Support for resetting lock while deserializing
1373 private void resetLock() {
1374 UNSAFE.putObjectVolatile(this, lockOffset, new ReentrantLock());
1375 }
1376 private static final sun.misc.Unsafe UNSAFE;
1377 private static final long lockOffset;
1378 static {
1379 try {
1380 UNSAFE = sun.misc.Unsafe.getUnsafe();
1381 Class<?> k = CopyOnWriteArrayList.class;
1382 lockOffset = UNSAFE.objectFieldOffset
1383 (k.getDeclaredField("lock"));
1384 } catch (Exception e) {
1385 throw new Error(e);
1386 }
1387 }
1388
1389 @Override
1390 @SuppressWarnings("unchecked")
1391 public void forEach(Consumer<? super E> action) {
1392 forEach(action, (E[]) getArray(), 0, size());
1393 }
1394
1395 private void forEach(Consumer<? super E> action,
1396 final E[] elements,
1397 final int from, final int to) {
1398 Objects.requireNonNull(action);
1399 for (int i = from; i < to; i++) {
1400 action.accept(elements[i]);
1401 }
1402 }
1403
1404 @Override
1405 public void sort(Comparator<? super E> c) {
1406 final ReentrantLock lock = this.lock;
1407 lock.lock();
1408 try {
1409 sort(c, 0, size());
1410 } finally {
1411 lock.unlock();
1412 }
1413 }
1414
1415 // must be called with this.lock held
1416 @SuppressWarnings("unchecked")
1417 private void sort(Comparator<? super E> c, final int from, final int to) {
1418 final E[] elements = (E[]) getArray();
1419 final E[] newElements = Arrays.copyOf(elements, elements.length);
1420 // only elements [from, to) are sorted
1421 Arrays.sort(newElements, from, to, c);
1422 setArray(newElements);
1423 }
1424
1425 @Override
1426 public boolean removeIf(Predicate<? super E> filter) {
1427 Objects.requireNonNull(filter);
1428 final ReentrantLock lock = this.lock;
1429 lock.lock();
1430 try {
1431 return removeIf(filter, 0, size()) > 0;
1432 } finally {
1433 lock.unlock();
1434 }
1435 }
1436
1437 // must be called with this.lock held
1438 private int removeIf(Predicate<? super E> filter, final int from, final int to) {
1439 Objects.requireNonNull(filter);
1440 final ReentrantLock lock = this.lock;
1441 lock.lock();
1442 try {
1443 @SuppressWarnings("unchecked")
1444 final E[] elements = (E[]) getArray();
1445
1446 // figure out which elements are to be removed
1447 // any exception thrown from the filter predicate at this stage
1448 // will leave the collection unmodified
1449 int removeCount = 0;
1450 final int range = to - from;
1451 final BitSet removeSet = new BitSet(range);
1452 for (int i = 0; i < range; i++) {
1453 final E element = elements[from + i];
1454 if (filter.test(element)) {
1455 // removeSet is zero-based to keep its size small
1456 removeSet.set(i);
1457 removeCount++;
1458 }
1459 }
1460
1461 // copy surviving elements into a new array
1462 if (removeCount > 0) {
1463 final int newSize = elements.length - removeCount;
1464 final int newRange = newSize - from;
1465 @SuppressWarnings("unchecked")
1466 final E[] newElements = (E[]) new Object[newSize];
1467 // copy elements before [from, to) unmodified
1468 for (int i = 0; i < from; i++) {
1469 newElements[i] = elements[i];
1470 }
1471 // elements [from, to) are subject to removal
1472 int j = 0;
1473 for (int i = 0; (i < range) && (j < newRange); i++) {
1474 i = removeSet.nextClearBit(i);
1475 if (i >= range) {
1476 break;
1477 }
1478 newElements[from + (j++)] = elements[from + i];
1479 }
1480 // copy any remaining elements beyond [from, to)
1481 j += from;
1482 for (int i = to; (i < elements.length) && (j < newSize); i++) {
1483 newElements[j++] = elements[i];
1484 }
1485 setArray(newElements);
1486 }
1487
1488 return removeCount;
1489 } finally {
1490 lock.unlock();
1491 }
1492 }
1493
1494 @Override
1495 public void replaceAll(UnaryOperator<E> operator) {
1496 Objects.requireNonNull(operator);
1497 final ReentrantLock lock = this.lock;
1498 lock.lock();
1499 try {
1500 replaceAll(operator, 0, size());
1501 } finally {
1502 lock.unlock();
1503 }
1504 }
1505
1506 // must be called with this.lock held
1507 @SuppressWarnings("unchecked")
1508 private void replaceAll(UnaryOperator<E> operator, final int from, final int to) {
1509 final E[] elements = (E[]) getArray();
1510 final E[] newElements = (E[]) new Object[elements.length];
1511 for (int i = 0; i < from; i++) {
1512 newElements[i] = elements[i];
1513 }
1514 // the operator is only applied to elements [from, to)
1515 for (int i = from; i < to; i++) {
1516 newElements[i] = operator.apply(elements[i]);
1517 }
1518 for (int i = to; i < elements.length; i++) {
1519 newElements[i] = elements[i];
1520 }
1521 setArray(newElements);
1522 }
1523 }
|