src/share/classes/java/util/concurrent/CopyOnWriteArrayList.java

Print this page
rev 6197 : [mq]: collections


  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>.


1297         }
1298 
1299         public int nextIndex() {
1300             return it.nextIndex() - offset;
1301         }
1302 
1303         public int previousIndex() {
1304             return it.previousIndex() - offset;
1305         }
1306 
1307         public void remove() {
1308             throw new UnsupportedOperationException();
1309         }
1310 
1311         public void set(E e) {
1312             throw new UnsupportedOperationException();
1313         }
1314 
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.Block;
  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>.


1300         }
1301 
1302         public int nextIndex() {
1303             return it.nextIndex() - offset;
1304         }
1305 
1306         public int previousIndex() {
1307             return it.previousIndex() - offset;
1308         }
1309 
1310         public void remove() {
1311             throw new UnsupportedOperationException();
1312         }
1313 
1314         public void set(E e) {
1315             throw new UnsupportedOperationException();
1316         }
1317 
1318         public void add(E e) {
1319             throw new UnsupportedOperationException();
1320         }
1321     }
1322 
1323     @SuppressWarnings("unchecked")
1324     public void forEach(Block<? super E> block) {
1325         Objects.requireNonNull(block);
1326         final Object[] elements = getArray();
1327         for (final Object element : elements) {
1328             block.accept((E) element);
1329         }
1330     }
1331 
1332     @Override
1333     public void sort(Comparator<? super E> c) {
1334         Objects.requireNonNull(c);
1335         final ReentrantLock lock = this.lock;
1336         lock.lock();
1337         try {
1338             @SuppressWarnings("unchecked")
1339             final E[] elements = (E[]) getArray();
1340             final E[] newElements = Arrays.copyOf(elements, elements.length);
1341             Arrays.sort(newElements, c);
1342             setArray(newElements);
1343         } finally {
1344             lock.unlock();
1345         }
1346     }
1347 
1348     @Override
1349     public boolean removeAll(Predicate<? super E> filter) {
1350         Objects.requireNonNull(filter);
1351         final ReentrantLock lock = this.lock;
1352         lock.lock();
1353         try {
1354             @SuppressWarnings("unchecked")
1355             final E[] elements = (E[]) getArray();
1356             final int size = elements.length;
1357 
1358             // figure out which elements are to be removed
1359             // any exception thrown from the filter predicate at this stage
1360             // will leave the collection unmodified
1361             int removeCount = 0;
1362             final BitSet removeSet = new BitSet(size);
1363             for (int i=0; i < size; i++) {
1364                 final E element = elements[i];
1365                 if (filter.test(element)) {
1366                     removeSet.set(i);
1367                     removeCount++;
1368                 }
1369             }
1370 
1371             // copy surviving elements into a new array
1372             final boolean anyToRemove = removeCount > 0;
1373             if (anyToRemove) {
1374                 final int newSize = size - removeCount;
1375                 final Object[] newElements = new Object[newSize];
1376                 for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
1377                     i = removeSet.nextClearBit(i);
1378                     newElements[j] = elements[i];
1379                 }
1380                 setArray(newElements);
1381             }
1382 
1383             return anyToRemove;
1384         } finally {
1385             lock.unlock();
1386         }
1387     }
1388 
1389     @Override
1390     public void replaceAll(UnaryOperator<E> operator) {
1391         Objects.requireNonNull(operator);
1392         final ReentrantLock lock = this.lock;
1393         lock.lock();
1394         try {
1395             @SuppressWarnings("unchecked")
1396             final E[] elements = (E[]) getArray();
1397             final int len = elements.length;
1398             @SuppressWarnings("unchecked")
1399             final E[] newElements = (E[]) new Object[len];
1400             for (int i=0; i < len; i++) {
1401                 newElements[i] = operator.operate(elements[i]);
1402             }
1403             setArray(newElements);
1404         } finally {
1405             lock.unlock();
1406         }
1407     }
1408 
1409     // Support for resetting lock while deserializing
1410     private void resetLock() {
1411         UNSAFE.putObjectVolatile(this, lockOffset, new ReentrantLock());
1412     }
1413     private static final sun.misc.Unsafe UNSAFE;
1414     private static final long lockOffset;
1415     static {
1416         try {
1417             UNSAFE = sun.misc.Unsafe.getUnsafe();
1418             Class<?> k = CopyOnWriteArrayList.class;
1419             lockOffset = UNSAFE.objectFieldOffset
1420                 (k.getDeclaredField("lock"));
1421         } catch (Exception e) {
1422             throw new Error(e);
1423         }
1424     }
1425 }