1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/rt/emul/compact/src/main/java/java/util/concurrent/CopyOnWriteArrayList.java Sat Mar 19 10:46:31 2016 +0100
1.3 @@ -0,0 +1,1340 @@
1.4 +/*
1.5 + * Copyright (c) 2003, 2011, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation. Oracle designates this
1.11 + * particular file as subject to the "Classpath" exception as provided
1.12 + * by Oracle in the LICENSE file that accompanied this code.
1.13 + *
1.14 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.15 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.16 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.17 + * version 2 for more details (a copy is included in the LICENSE file that
1.18 + * accompanied this code).
1.19 + *
1.20 + * You should have received a copy of the GNU General Public License version
1.21 + * 2 along with this work; if not, write to the Free Software Foundation,
1.22 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.23 + *
1.24 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.25 + * or visit www.oracle.com if you need additional information or have any
1.26 + * questions.
1.27 + */
1.28 +
1.29 +/*
1.30 + * Written by Doug Lea with assistance from members of JCP JSR-166
1.31 + * Expert Group. Adapted and released, under explicit permission,
1.32 + * from JDK ArrayList.java which carries the following copyright:
1.33 + *
1.34 + * Copyright 1997 by Sun Microsystems, Inc.,
1.35 + * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
1.36 + * All rights reserved.
1.37 + */
1.38 +
1.39 +package java.util.concurrent;
1.40 +import java.util.*;
1.41 +import java.util.concurrent.locks.*;
1.42 +import sun.misc.Unsafe;
1.43 +
1.44 +/**
1.45 + * A thread-safe variant of {@link java.util.ArrayList} in which all mutative
1.46 + * operations (<tt>add</tt>, <tt>set</tt>, and so on) are implemented by
1.47 + * making a fresh copy of the underlying array.
1.48 + *
1.49 + * <p> This is ordinarily too costly, but may be <em>more</em> efficient
1.50 + * than alternatives when traversal operations vastly outnumber
1.51 + * mutations, and is useful when you cannot or don't want to
1.52 + * synchronize traversals, yet need to preclude interference among
1.53 + * concurrent threads. The "snapshot" style iterator method uses a
1.54 + * reference to the state of the array at the point that the iterator
1.55 + * was created. This array never changes during the lifetime of the
1.56 + * iterator, so interference is impossible and the iterator is
1.57 + * guaranteed not to throw <tt>ConcurrentModificationException</tt>.
1.58 + * The iterator will not reflect additions, removals, or changes to
1.59 + * the list since the iterator was created. Element-changing
1.60 + * operations on iterators themselves (<tt>remove</tt>, <tt>set</tt>, and
1.61 + * <tt>add</tt>) are not supported. These methods throw
1.62 + * <tt>UnsupportedOperationException</tt>.
1.63 + *
1.64 + * <p>All elements are permitted, including <tt>null</tt>.
1.65 + *
1.66 + * <p>Memory consistency effects: As with other concurrent
1.67 + * collections, actions in a thread prior to placing an object into a
1.68 + * {@code CopyOnWriteArrayList}
1.69 + * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>
1.70 + * actions subsequent to the access or removal of that element from
1.71 + * the {@code CopyOnWriteArrayList} in another thread.
1.72 + *
1.73 + * <p>This class is a member of the
1.74 + * <a href="{@docRoot}/../technotes/guides/collections/index.html">
1.75 + * Java Collections Framework</a>.
1.76 + *
1.77 + * @since 1.5
1.78 + * @author Doug Lea
1.79 + * @param <E> the type of elements held in this collection
1.80 + */
1.81 +public class CopyOnWriteArrayList<E>
1.82 + implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
1.83 + private static final long serialVersionUID = 8673264195747942595L;
1.84 +
1.85 + /** The lock protecting all mutators */
1.86 + transient final ReentrantLock lock = new ReentrantLock();
1.87 +
1.88 + /** The array, accessed only via getArray/setArray. */
1.89 + private volatile transient Object[] array;
1.90 +
1.91 + /**
1.92 + * Gets the array. Non-private so as to also be accessible
1.93 + * from CopyOnWriteArraySet class.
1.94 + */
1.95 + final Object[] getArray() {
1.96 + return array;
1.97 + }
1.98 +
1.99 + /**
1.100 + * Sets the array.
1.101 + */
1.102 + final void setArray(Object[] a) {
1.103 + array = a;
1.104 + }
1.105 +
1.106 + /**
1.107 + * Creates an empty list.
1.108 + */
1.109 + public CopyOnWriteArrayList() {
1.110 + setArray(new Object[0]);
1.111 + }
1.112 +
1.113 + /**
1.114 + * Creates a list containing the elements of the specified
1.115 + * collection, in the order they are returned by the collection's
1.116 + * iterator.
1.117 + *
1.118 + * @param c the collection of initially held elements
1.119 + * @throws NullPointerException if the specified collection is null
1.120 + */
1.121 + public CopyOnWriteArrayList(Collection<? extends E> c) {
1.122 + Object[] elements = c.toArray();
1.123 + // c.toArray might (incorrectly) not return Object[] (see 6260652)
1.124 + if (elements.getClass() != Object[].class)
1.125 + elements = Arrays.copyOf(elements, elements.length, Object[].class);
1.126 + setArray(elements);
1.127 + }
1.128 +
1.129 + /**
1.130 + * Creates a list holding a copy of the given array.
1.131 + *
1.132 + * @param toCopyIn the array (a copy of this array is used as the
1.133 + * internal array)
1.134 + * @throws NullPointerException if the specified array is null
1.135 + */
1.136 + public CopyOnWriteArrayList(E[] toCopyIn) {
1.137 + setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
1.138 + }
1.139 +
1.140 + /**
1.141 + * Returns the number of elements in this list.
1.142 + *
1.143 + * @return the number of elements in this list
1.144 + */
1.145 + public int size() {
1.146 + return getArray().length;
1.147 + }
1.148 +
1.149 + /**
1.150 + * Returns <tt>true</tt> if this list contains no elements.
1.151 + *
1.152 + * @return <tt>true</tt> if this list contains no elements
1.153 + */
1.154 + public boolean isEmpty() {
1.155 + return size() == 0;
1.156 + }
1.157 +
1.158 + /**
1.159 + * Test for equality, coping with nulls.
1.160 + */
1.161 + private static boolean eq(Object o1, Object o2) {
1.162 + return (o1 == null ? o2 == null : o1.equals(o2));
1.163 + }
1.164 +
1.165 + /**
1.166 + * static version of indexOf, to allow repeated calls without
1.167 + * needing to re-acquire array each time.
1.168 + * @param o element to search for
1.169 + * @param elements the array
1.170 + * @param index first index to search
1.171 + * @param fence one past last index to search
1.172 + * @return index of element, or -1 if absent
1.173 + */
1.174 + private static int indexOf(Object o, Object[] elements,
1.175 + int index, int fence) {
1.176 + if (o == null) {
1.177 + for (int i = index; i < fence; i++)
1.178 + if (elements[i] == null)
1.179 + return i;
1.180 + } else {
1.181 + for (int i = index; i < fence; i++)
1.182 + if (o.equals(elements[i]))
1.183 + return i;
1.184 + }
1.185 + return -1;
1.186 + }
1.187 +
1.188 + /**
1.189 + * static version of lastIndexOf.
1.190 + * @param o element to search for
1.191 + * @param elements the array
1.192 + * @param index first index to search
1.193 + * @return index of element, or -1 if absent
1.194 + */
1.195 + private static int lastIndexOf(Object o, Object[] elements, int index) {
1.196 + if (o == null) {
1.197 + for (int i = index; i >= 0; i--)
1.198 + if (elements[i] == null)
1.199 + return i;
1.200 + } else {
1.201 + for (int i = index; i >= 0; i--)
1.202 + if (o.equals(elements[i]))
1.203 + return i;
1.204 + }
1.205 + return -1;
1.206 + }
1.207 +
1.208 + /**
1.209 + * Returns <tt>true</tt> if this list contains the specified element.
1.210 + * More formally, returns <tt>true</tt> if and only if this list contains
1.211 + * at least one element <tt>e</tt> such that
1.212 + * <tt>(o==null ? e==null : o.equals(e))</tt>.
1.213 + *
1.214 + * @param o element whose presence in this list is to be tested
1.215 + * @return <tt>true</tt> if this list contains the specified element
1.216 + */
1.217 + public boolean contains(Object o) {
1.218 + Object[] elements = getArray();
1.219 + return indexOf(o, elements, 0, elements.length) >= 0;
1.220 + }
1.221 +
1.222 + /**
1.223 + * {@inheritDoc}
1.224 + */
1.225 + public int indexOf(Object o) {
1.226 + Object[] elements = getArray();
1.227 + return indexOf(o, elements, 0, elements.length);
1.228 + }
1.229 +
1.230 + /**
1.231 + * Returns the index of the first occurrence of the specified element in
1.232 + * this list, searching forwards from <tt>index</tt>, or returns -1 if
1.233 + * the element is not found.
1.234 + * More formally, returns the lowest index <tt>i</tt> such that
1.235 + * <tt>(i >= index && (e==null ? get(i)==null : e.equals(get(i))))</tt>,
1.236 + * or -1 if there is no such index.
1.237 + *
1.238 + * @param e element to search for
1.239 + * @param index index to start searching from
1.240 + * @return the index of the first occurrence of the element in
1.241 + * this list at position <tt>index</tt> or later in the list;
1.242 + * <tt>-1</tt> if the element is not found.
1.243 + * @throws IndexOutOfBoundsException if the specified index is negative
1.244 + */
1.245 + public int indexOf(E e, int index) {
1.246 + Object[] elements = getArray();
1.247 + return indexOf(e, elements, index, elements.length);
1.248 + }
1.249 +
1.250 + /**
1.251 + * {@inheritDoc}
1.252 + */
1.253 + public int lastIndexOf(Object o) {
1.254 + Object[] elements = getArray();
1.255 + return lastIndexOf(o, elements, elements.length - 1);
1.256 + }
1.257 +
1.258 + /**
1.259 + * Returns the index of the last occurrence of the specified element in
1.260 + * this list, searching backwards from <tt>index</tt>, or returns -1 if
1.261 + * the element is not found.
1.262 + * More formally, returns the highest index <tt>i</tt> such that
1.263 + * <tt>(i <= index && (e==null ? get(i)==null : e.equals(get(i))))</tt>,
1.264 + * or -1 if there is no such index.
1.265 + *
1.266 + * @param e element to search for
1.267 + * @param index index to start searching backwards from
1.268 + * @return the index of the last occurrence of the element at position
1.269 + * less than or equal to <tt>index</tt> in this list;
1.270 + * -1 if the element is not found.
1.271 + * @throws IndexOutOfBoundsException if the specified index is greater
1.272 + * than or equal to the current size of this list
1.273 + */
1.274 + public int lastIndexOf(E e, int index) {
1.275 + Object[] elements = getArray();
1.276 + return lastIndexOf(e, elements, index);
1.277 + }
1.278 +
1.279 + /**
1.280 + * Returns a shallow copy of this list. (The elements themselves
1.281 + * are not copied.)
1.282 + *
1.283 + * @return a clone of this list
1.284 + */
1.285 + public Object clone() {
1.286 + try {
1.287 + CopyOnWriteArrayList c = (CopyOnWriteArrayList)(super.clone());
1.288 + c.resetLock();
1.289 + return c;
1.290 + } catch (CloneNotSupportedException e) {
1.291 + // this shouldn't happen, since we are Cloneable
1.292 + throw new InternalError();
1.293 + }
1.294 + }
1.295 +
1.296 + /**
1.297 + * Returns an array containing all of the elements in this list
1.298 + * in proper sequence (from first to last element).
1.299 + *
1.300 + * <p>The returned array will be "safe" in that no references to it are
1.301 + * maintained by this list. (In other words, this method must allocate
1.302 + * a new array). The caller is thus free to modify the returned array.
1.303 + *
1.304 + * <p>This method acts as bridge between array-based and collection-based
1.305 + * APIs.
1.306 + *
1.307 + * @return an array containing all the elements in this list
1.308 + */
1.309 + public Object[] toArray() {
1.310 + Object[] elements = getArray();
1.311 + return Arrays.copyOf(elements, elements.length);
1.312 + }
1.313 +
1.314 + /**
1.315 + * Returns an array containing all of the elements in this list in
1.316 + * proper sequence (from first to last element); the runtime type of
1.317 + * the returned array is that of the specified array. If the list fits
1.318 + * in the specified array, it is returned therein. Otherwise, a new
1.319 + * array is allocated with the runtime type of the specified array and
1.320 + * the size of this list.
1.321 + *
1.322 + * <p>If this list fits in the specified array with room to spare
1.323 + * (i.e., the array has more elements than this list), the element in
1.324 + * the array immediately following the end of the list is set to
1.325 + * <tt>null</tt>. (This is useful in determining the length of this
1.326 + * list <i>only</i> if the caller knows that this list does not contain
1.327 + * any null elements.)
1.328 + *
1.329 + * <p>Like the {@link #toArray()} method, this method acts as bridge between
1.330 + * array-based and collection-based APIs. Further, this method allows
1.331 + * precise control over the runtime type of the output array, and may,
1.332 + * under certain circumstances, be used to save allocation costs.
1.333 + *
1.334 + * <p>Suppose <tt>x</tt> is a list known to contain only strings.
1.335 + * The following code can be used to dump the list into a newly
1.336 + * allocated array of <tt>String</tt>:
1.337 + *
1.338 + * <pre>
1.339 + * String[] y = x.toArray(new String[0]);</pre>
1.340 + *
1.341 + * Note that <tt>toArray(new Object[0])</tt> is identical in function to
1.342 + * <tt>toArray()</tt>.
1.343 + *
1.344 + * @param a the array into which the elements of the list are to
1.345 + * be stored, if it is big enough; otherwise, a new array of the
1.346 + * same runtime type is allocated for this purpose.
1.347 + * @return an array containing all the elements in this list
1.348 + * @throws ArrayStoreException if the runtime type of the specified array
1.349 + * is not a supertype of the runtime type of every element in
1.350 + * this list
1.351 + * @throws NullPointerException if the specified array is null
1.352 + */
1.353 + @SuppressWarnings("unchecked")
1.354 + public <T> T[] toArray(T a[]) {
1.355 + Object[] elements = getArray();
1.356 + int len = elements.length;
1.357 + if (a.length < len)
1.358 + return (T[]) Arrays.copyOf(elements, len, a.getClass());
1.359 + else {
1.360 + System.arraycopy(elements, 0, a, 0, len);
1.361 + if (a.length > len)
1.362 + a[len] = null;
1.363 + return a;
1.364 + }
1.365 + }
1.366 +
1.367 + // Positional Access Operations
1.368 +
1.369 + @SuppressWarnings("unchecked")
1.370 + private E get(Object[] a, int index) {
1.371 + return (E) a[index];
1.372 + }
1.373 +
1.374 + /**
1.375 + * {@inheritDoc}
1.376 + *
1.377 + * @throws IndexOutOfBoundsException {@inheritDoc}
1.378 + */
1.379 + public E get(int index) {
1.380 + return get(getArray(), index);
1.381 + }
1.382 +
1.383 + /**
1.384 + * Replaces the element at the specified position in this list with the
1.385 + * specified element.
1.386 + *
1.387 + * @throws IndexOutOfBoundsException {@inheritDoc}
1.388 + */
1.389 + public E set(int index, E element) {
1.390 + final ReentrantLock lock = this.lock;
1.391 + lock.lock();
1.392 + try {
1.393 + Object[] elements = getArray();
1.394 + E oldValue = get(elements, index);
1.395 +
1.396 + if (oldValue != element) {
1.397 + int len = elements.length;
1.398 + Object[] newElements = Arrays.copyOf(elements, len);
1.399 + newElements[index] = element;
1.400 + setArray(newElements);
1.401 + } else {
1.402 + // Not quite a no-op; ensures volatile write semantics
1.403 + setArray(elements);
1.404 + }
1.405 + return oldValue;
1.406 + } finally {
1.407 + lock.unlock();
1.408 + }
1.409 + }
1.410 +
1.411 + /**
1.412 + * Appends the specified element to the end of this list.
1.413 + *
1.414 + * @param e element to be appended to this list
1.415 + * @return <tt>true</tt> (as specified by {@link Collection#add})
1.416 + */
1.417 + public boolean add(E e) {
1.418 + final ReentrantLock lock = this.lock;
1.419 + lock.lock();
1.420 + try {
1.421 + Object[] elements = getArray();
1.422 + int len = elements.length;
1.423 + Object[] newElements = Arrays.copyOf(elements, len + 1);
1.424 + newElements[len] = e;
1.425 + setArray(newElements);
1.426 + return true;
1.427 + } finally {
1.428 + lock.unlock();
1.429 + }
1.430 + }
1.431 +
1.432 + /**
1.433 + * Inserts the specified element at the specified position in this
1.434 + * list. Shifts the element currently at that position (if any) and
1.435 + * any subsequent elements to the right (adds one to their indices).
1.436 + *
1.437 + * @throws IndexOutOfBoundsException {@inheritDoc}
1.438 + */
1.439 + public void add(int index, E element) {
1.440 + final ReentrantLock lock = this.lock;
1.441 + lock.lock();
1.442 + try {
1.443 + Object[] elements = getArray();
1.444 + int len = elements.length;
1.445 + if (index > len || index < 0)
1.446 + throw new IndexOutOfBoundsException("Index: "+index+
1.447 + ", Size: "+len);
1.448 + Object[] newElements;
1.449 + int numMoved = len - index;
1.450 + if (numMoved == 0)
1.451 + newElements = Arrays.copyOf(elements, len + 1);
1.452 + else {
1.453 + newElements = new Object[len + 1];
1.454 + System.arraycopy(elements, 0, newElements, 0, index);
1.455 + System.arraycopy(elements, index, newElements, index + 1,
1.456 + numMoved);
1.457 + }
1.458 + newElements[index] = element;
1.459 + setArray(newElements);
1.460 + } finally {
1.461 + lock.unlock();
1.462 + }
1.463 + }
1.464 +
1.465 + /**
1.466 + * Removes the element at the specified position in this list.
1.467 + * Shifts any subsequent elements to the left (subtracts one from their
1.468 + * indices). Returns the element that was removed from the list.
1.469 + *
1.470 + * @throws IndexOutOfBoundsException {@inheritDoc}
1.471 + */
1.472 + public E remove(int index) {
1.473 + final ReentrantLock lock = this.lock;
1.474 + lock.lock();
1.475 + try {
1.476 + Object[] elements = getArray();
1.477 + int len = elements.length;
1.478 + E oldValue = get(elements, index);
1.479 + int numMoved = len - index - 1;
1.480 + if (numMoved == 0)
1.481 + setArray(Arrays.copyOf(elements, len - 1));
1.482 + else {
1.483 + Object[] newElements = new Object[len - 1];
1.484 + System.arraycopy(elements, 0, newElements, 0, index);
1.485 + System.arraycopy(elements, index + 1, newElements, index,
1.486 + numMoved);
1.487 + setArray(newElements);
1.488 + }
1.489 + return oldValue;
1.490 + } finally {
1.491 + lock.unlock();
1.492 + }
1.493 + }
1.494 +
1.495 + /**
1.496 + * Removes the first occurrence of the specified element from this list,
1.497 + * if it is present. If this list does not contain the element, it is
1.498 + * unchanged. More formally, removes the element with the lowest index
1.499 + * <tt>i</tt> such that
1.500 + * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
1.501 + * (if such an element exists). Returns <tt>true</tt> if this list
1.502 + * contained the specified element (or equivalently, if this list
1.503 + * changed as a result of the call).
1.504 + *
1.505 + * @param o element to be removed from this list, if present
1.506 + * @return <tt>true</tt> if this list contained the specified element
1.507 + */
1.508 + public boolean remove(Object o) {
1.509 + final ReentrantLock lock = this.lock;
1.510 + lock.lock();
1.511 + try {
1.512 + Object[] elements = getArray();
1.513 + int len = elements.length;
1.514 + if (len != 0) {
1.515 + // Copy while searching for element to remove
1.516 + // This wins in the normal case of element being present
1.517 + int newlen = len - 1;
1.518 + Object[] newElements = new Object[newlen];
1.519 +
1.520 + for (int i = 0; i < newlen; ++i) {
1.521 + if (eq(o, elements[i])) {
1.522 + // found one; copy remaining and exit
1.523 + for (int k = i + 1; k < len; ++k)
1.524 + newElements[k-1] = elements[k];
1.525 + setArray(newElements);
1.526 + return true;
1.527 + } else
1.528 + newElements[i] = elements[i];
1.529 + }
1.530 +
1.531 + // special handling for last cell
1.532 + if (eq(o, elements[newlen])) {
1.533 + setArray(newElements);
1.534 + return true;
1.535 + }
1.536 + }
1.537 + return false;
1.538 + } finally {
1.539 + lock.unlock();
1.540 + }
1.541 + }
1.542 +
1.543 + /**
1.544 + * Removes from this list all of the elements whose index is between
1.545 + * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
1.546 + * Shifts any succeeding elements to the left (reduces their index).
1.547 + * This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements.
1.548 + * (If <tt>toIndex==fromIndex</tt>, this operation has no effect.)
1.549 + *
1.550 + * @param fromIndex index of first element to be removed
1.551 + * @param toIndex index after last element to be removed
1.552 + * @throws IndexOutOfBoundsException if fromIndex or toIndex out of range
1.553 + * ({@code{fromIndex < 0 || toIndex > size() || toIndex < fromIndex})
1.554 + */
1.555 + private void removeRange(int fromIndex, int toIndex) {
1.556 + final ReentrantLock lock = this.lock;
1.557 + lock.lock();
1.558 + try {
1.559 + Object[] elements = getArray();
1.560 + int len = elements.length;
1.561 +
1.562 + if (fromIndex < 0 || toIndex > len || toIndex < fromIndex)
1.563 + throw new IndexOutOfBoundsException();
1.564 + int newlen = len - (toIndex - fromIndex);
1.565 + int numMoved = len - toIndex;
1.566 + if (numMoved == 0)
1.567 + setArray(Arrays.copyOf(elements, newlen));
1.568 + else {
1.569 + Object[] newElements = new Object[newlen];
1.570 + System.arraycopy(elements, 0, newElements, 0, fromIndex);
1.571 + System.arraycopy(elements, toIndex, newElements,
1.572 + fromIndex, numMoved);
1.573 + setArray(newElements);
1.574 + }
1.575 + } finally {
1.576 + lock.unlock();
1.577 + }
1.578 + }
1.579 +
1.580 + /**
1.581 + * Append the element if not present.
1.582 + *
1.583 + * @param e element to be added to this list, if absent
1.584 + * @return <tt>true</tt> if the element was added
1.585 + */
1.586 + public boolean addIfAbsent(E e) {
1.587 + final ReentrantLock lock = this.lock;
1.588 + lock.lock();
1.589 + try {
1.590 + // Copy while checking if already present.
1.591 + // This wins in the most common case where it is not present
1.592 + Object[] elements = getArray();
1.593 + int len = elements.length;
1.594 + Object[] newElements = new Object[len + 1];
1.595 + for (int i = 0; i < len; ++i) {
1.596 + if (eq(e, elements[i]))
1.597 + return false; // exit, throwing away copy
1.598 + else
1.599 + newElements[i] = elements[i];
1.600 + }
1.601 + newElements[len] = e;
1.602 + setArray(newElements);
1.603 + return true;
1.604 + } finally {
1.605 + lock.unlock();
1.606 + }
1.607 + }
1.608 +
1.609 + /**
1.610 + * Returns <tt>true</tt> if this list contains all of the elements of the
1.611 + * specified collection.
1.612 + *
1.613 + * @param c collection to be checked for containment in this list
1.614 + * @return <tt>true</tt> if this list contains all of the elements of the
1.615 + * specified collection
1.616 + * @throws NullPointerException if the specified collection is null
1.617 + * @see #contains(Object)
1.618 + */
1.619 + public boolean containsAll(Collection<?> c) {
1.620 + Object[] elements = getArray();
1.621 + int len = elements.length;
1.622 + for (Object e : c) {
1.623 + if (indexOf(e, elements, 0, len) < 0)
1.624 + return false;
1.625 + }
1.626 + return true;
1.627 + }
1.628 +
1.629 + /**
1.630 + * Removes from this list all of its elements that are contained in
1.631 + * the specified collection. This is a particularly expensive operation
1.632 + * in this class because of the need for an internal temporary array.
1.633 + *
1.634 + * @param c collection containing elements to be removed from this list
1.635 + * @return <tt>true</tt> if this list changed as a result of the call
1.636 + * @throws ClassCastException if the class of an element of this list
1.637 + * is incompatible with the specified collection
1.638 + * (<a href="../Collection.html#optional-restrictions">optional</a>)
1.639 + * @throws NullPointerException if this list contains a null element and the
1.640 + * specified collection does not permit null elements
1.641 + * (<a href="../Collection.html#optional-restrictions">optional</a>),
1.642 + * or if the specified collection is null
1.643 + * @see #remove(Object)
1.644 + */
1.645 + public boolean removeAll(Collection<?> c) {
1.646 + final ReentrantLock lock = this.lock;
1.647 + lock.lock();
1.648 + try {
1.649 + Object[] elements = getArray();
1.650 + int len = elements.length;
1.651 + if (len != 0) {
1.652 + // temp array holds those elements we know we want to keep
1.653 + int newlen = 0;
1.654 + Object[] temp = new Object[len];
1.655 + for (int i = 0; i < len; ++i) {
1.656 + Object element = elements[i];
1.657 + if (!c.contains(element))
1.658 + temp[newlen++] = element;
1.659 + }
1.660 + if (newlen != len) {
1.661 + setArray(Arrays.copyOf(temp, newlen));
1.662 + return true;
1.663 + }
1.664 + }
1.665 + return false;
1.666 + } finally {
1.667 + lock.unlock();
1.668 + }
1.669 + }
1.670 +
1.671 + /**
1.672 + * Retains only the elements in this list that are contained in the
1.673 + * specified collection. In other words, removes from this list all of
1.674 + * its elements that are not contained in the specified collection.
1.675 + *
1.676 + * @param c collection containing elements to be retained in this list
1.677 + * @return <tt>true</tt> if this list changed as a result of the call
1.678 + * @throws ClassCastException if the class of an element of this list
1.679 + * is incompatible with the specified collection
1.680 + * (<a href="../Collection.html#optional-restrictions">optional</a>)
1.681 + * @throws NullPointerException if this list contains a null element and the
1.682 + * specified collection does not permit null elements
1.683 + * (<a href="../Collection.html#optional-restrictions">optional</a>),
1.684 + * or if the specified collection is null
1.685 + * @see #remove(Object)
1.686 + */
1.687 + public boolean retainAll(Collection<?> c) {
1.688 + final ReentrantLock lock = this.lock;
1.689 + lock.lock();
1.690 + try {
1.691 + Object[] elements = getArray();
1.692 + int len = elements.length;
1.693 + if (len != 0) {
1.694 + // temp array holds those elements we know we want to keep
1.695 + int newlen = 0;
1.696 + Object[] temp = new Object[len];
1.697 + for (int i = 0; i < len; ++i) {
1.698 + Object element = elements[i];
1.699 + if (c.contains(element))
1.700 + temp[newlen++] = element;
1.701 + }
1.702 + if (newlen != len) {
1.703 + setArray(Arrays.copyOf(temp, newlen));
1.704 + return true;
1.705 + }
1.706 + }
1.707 + return false;
1.708 + } finally {
1.709 + lock.unlock();
1.710 + }
1.711 + }
1.712 +
1.713 + /**
1.714 + * Appends all of the elements in the specified collection that
1.715 + * are not already contained in this list, to the end of
1.716 + * this list, in the order that they are returned by the
1.717 + * specified collection's iterator.
1.718 + *
1.719 + * @param c collection containing elements to be added to this list
1.720 + * @return the number of elements added
1.721 + * @throws NullPointerException if the specified collection is null
1.722 + * @see #addIfAbsent(Object)
1.723 + */
1.724 + public int addAllAbsent(Collection<? extends E> c) {
1.725 + Object[] cs = c.toArray();
1.726 + if (cs.length == 0)
1.727 + return 0;
1.728 + Object[] uniq = new Object[cs.length];
1.729 + final ReentrantLock lock = this.lock;
1.730 + lock.lock();
1.731 + try {
1.732 + Object[] elements = getArray();
1.733 + int len = elements.length;
1.734 + int added = 0;
1.735 + for (int i = 0; i < cs.length; ++i) { // scan for duplicates
1.736 + Object e = cs[i];
1.737 + if (indexOf(e, elements, 0, len) < 0 &&
1.738 + indexOf(e, uniq, 0, added) < 0)
1.739 + uniq[added++] = e;
1.740 + }
1.741 + if (added > 0) {
1.742 + Object[] newElements = Arrays.copyOf(elements, len + added);
1.743 + System.arraycopy(uniq, 0, newElements, len, added);
1.744 + setArray(newElements);
1.745 + }
1.746 + return added;
1.747 + } finally {
1.748 + lock.unlock();
1.749 + }
1.750 + }
1.751 +
1.752 + /**
1.753 + * Removes all of the elements from this list.
1.754 + * The list will be empty after this call returns.
1.755 + */
1.756 + public void clear() {
1.757 + final ReentrantLock lock = this.lock;
1.758 + lock.lock();
1.759 + try {
1.760 + setArray(new Object[0]);
1.761 + } finally {
1.762 + lock.unlock();
1.763 + }
1.764 + }
1.765 +
1.766 + /**
1.767 + * Appends all of the elements in the specified collection to the end
1.768 + * of this list, in the order that they are returned by the specified
1.769 + * collection's iterator.
1.770 + *
1.771 + * @param c collection containing elements to be added to this list
1.772 + * @return <tt>true</tt> if this list changed as a result of the call
1.773 + * @throws NullPointerException if the specified collection is null
1.774 + * @see #add(Object)
1.775 + */
1.776 + public boolean addAll(Collection<? extends E> c) {
1.777 + Object[] cs = c.toArray();
1.778 + if (cs.length == 0)
1.779 + return false;
1.780 + final ReentrantLock lock = this.lock;
1.781 + lock.lock();
1.782 + try {
1.783 + Object[] elements = getArray();
1.784 + int len = elements.length;
1.785 + Object[] newElements = Arrays.copyOf(elements, len + cs.length);
1.786 + System.arraycopy(cs, 0, newElements, len, cs.length);
1.787 + setArray(newElements);
1.788 + return true;
1.789 + } finally {
1.790 + lock.unlock();
1.791 + }
1.792 + }
1.793 +
1.794 + /**
1.795 + * Inserts all of the elements in the specified collection into this
1.796 + * list, starting at the specified position. Shifts the element
1.797 + * currently at that position (if any) and any subsequent elements to
1.798 + * the right (increases their indices). The new elements will appear
1.799 + * in this list in the order that they are returned by the
1.800 + * specified collection's iterator.
1.801 + *
1.802 + * @param index index at which to insert the first element
1.803 + * from the specified collection
1.804 + * @param c collection containing elements to be added to this list
1.805 + * @return <tt>true</tt> if this list changed as a result of the call
1.806 + * @throws IndexOutOfBoundsException {@inheritDoc}
1.807 + * @throws NullPointerException if the specified collection is null
1.808 + * @see #add(int,Object)
1.809 + */
1.810 + public boolean addAll(int index, Collection<? extends E> c) {
1.811 + Object[] cs = c.toArray();
1.812 + final ReentrantLock lock = this.lock;
1.813 + lock.lock();
1.814 + try {
1.815 + Object[] elements = getArray();
1.816 + int len = elements.length;
1.817 + if (index > len || index < 0)
1.818 + throw new IndexOutOfBoundsException("Index: "+index+
1.819 + ", Size: "+len);
1.820 + if (cs.length == 0)
1.821 + return false;
1.822 + int numMoved = len - index;
1.823 + Object[] newElements;
1.824 + if (numMoved == 0)
1.825 + newElements = Arrays.copyOf(elements, len + cs.length);
1.826 + else {
1.827 + newElements = new Object[len + cs.length];
1.828 + System.arraycopy(elements, 0, newElements, 0, index);
1.829 + System.arraycopy(elements, index,
1.830 + newElements, index + cs.length,
1.831 + numMoved);
1.832 + }
1.833 + System.arraycopy(cs, 0, newElements, index, cs.length);
1.834 + setArray(newElements);
1.835 + return true;
1.836 + } finally {
1.837 + lock.unlock();
1.838 + }
1.839 + }
1.840 +
1.841 + /**
1.842 + * Saves the state of the list to a stream (that is, serializes it).
1.843 + *
1.844 + * @serialData The length of the array backing the list is emitted
1.845 + * (int), followed by all of its elements (each an Object)
1.846 + * in the proper order.
1.847 + * @param s the stream
1.848 + */
1.849 + private void writeObject(java.io.ObjectOutputStream s)
1.850 + throws java.io.IOException{
1.851 +
1.852 + s.defaultWriteObject();
1.853 +
1.854 + Object[] elements = getArray();
1.855 + // Write out array length
1.856 + s.writeInt(elements.length);
1.857 +
1.858 + // Write out all elements in the proper order.
1.859 + for (Object element : elements)
1.860 + s.writeObject(element);
1.861 + }
1.862 +
1.863 + /**
1.864 + * Reconstitutes the list from a stream (that is, deserializes it).
1.865 + *
1.866 + * @param s the stream
1.867 + */
1.868 + private void readObject(java.io.ObjectInputStream s)
1.869 + throws java.io.IOException, ClassNotFoundException {
1.870 +
1.871 + s.defaultReadObject();
1.872 +
1.873 + // bind to new lock
1.874 + resetLock();
1.875 +
1.876 + // Read in array length and allocate array
1.877 + int len = s.readInt();
1.878 + Object[] elements = new Object[len];
1.879 +
1.880 + // Read in all elements in the proper order.
1.881 + for (int i = 0; i < len; i++)
1.882 + elements[i] = s.readObject();
1.883 + setArray(elements);
1.884 + }
1.885 +
1.886 + /**
1.887 + * Returns a string representation of this list. The string
1.888 + * representation consists of the string representations of the list's
1.889 + * elements in the order they are returned by its iterator, enclosed in
1.890 + * square brackets (<tt>"[]"</tt>). Adjacent elements are separated by
1.891 + * the characters <tt>", "</tt> (comma and space). Elements are
1.892 + * converted to strings as by {@link String#valueOf(Object)}.
1.893 + *
1.894 + * @return a string representation of this list
1.895 + */
1.896 + public String toString() {
1.897 + return Arrays.toString(getArray());
1.898 + }
1.899 +
1.900 + /**
1.901 + * Compares the specified object with this list for equality.
1.902 + * Returns {@code true} if the specified object is the same object
1.903 + * as this object, or if it is also a {@link List} and the sequence
1.904 + * of elements returned by an {@linkplain List#iterator() iterator}
1.905 + * over the specified list is the same as the sequence returned by
1.906 + * an iterator over this list. The two sequences are considered to
1.907 + * be the same if they have the same length and corresponding
1.908 + * elements at the same position in the sequence are <em>equal</em>.
1.909 + * Two elements {@code e1} and {@code e2} are considered
1.910 + * <em>equal</em> if {@code (e1==null ? e2==null : e1.equals(e2))}.
1.911 + *
1.912 + * @param o the object to be compared for equality with this list
1.913 + * @return {@code true} if the specified object is equal to this list
1.914 + */
1.915 + public boolean equals(Object o) {
1.916 + if (o == this)
1.917 + return true;
1.918 + if (!(o instanceof List))
1.919 + return false;
1.920 +
1.921 + List<?> list = (List<?>)(o);
1.922 + Iterator<?> it = list.iterator();
1.923 + Object[] elements = getArray();
1.924 + int len = elements.length;
1.925 + for (int i = 0; i < len; ++i)
1.926 + if (!it.hasNext() || !eq(elements[i], it.next()))
1.927 + return false;
1.928 + if (it.hasNext())
1.929 + return false;
1.930 + return true;
1.931 + }
1.932 +
1.933 + /**
1.934 + * Returns the hash code value for this list.
1.935 + *
1.936 + * <p>This implementation uses the definition in {@link List#hashCode}.
1.937 + *
1.938 + * @return the hash code value for this list
1.939 + */
1.940 + public int hashCode() {
1.941 + int hashCode = 1;
1.942 + Object[] elements = getArray();
1.943 + int len = elements.length;
1.944 + for (int i = 0; i < len; ++i) {
1.945 + Object obj = elements[i];
1.946 + hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
1.947 + }
1.948 + return hashCode;
1.949 + }
1.950 +
1.951 + /**
1.952 + * Returns an iterator over the elements in this list in proper sequence.
1.953 + *
1.954 + * <p>The returned iterator provides a snapshot of the state of the list
1.955 + * when the iterator was constructed. No synchronization is needed while
1.956 + * traversing the iterator. The iterator does <em>NOT</em> support the
1.957 + * <tt>remove</tt> method.
1.958 + *
1.959 + * @return an iterator over the elements in this list in proper sequence
1.960 + */
1.961 + public Iterator<E> iterator() {
1.962 + return new COWIterator<E>(getArray(), 0);
1.963 + }
1.964 +
1.965 + /**
1.966 + * {@inheritDoc}
1.967 + *
1.968 + * <p>The returned iterator provides a snapshot of the state of the list
1.969 + * when the iterator was constructed. No synchronization is needed while
1.970 + * traversing the iterator. The iterator does <em>NOT</em> support the
1.971 + * <tt>remove</tt>, <tt>set</tt> or <tt>add</tt> methods.
1.972 + */
1.973 + public ListIterator<E> listIterator() {
1.974 + return new COWIterator<E>(getArray(), 0);
1.975 + }
1.976 +
1.977 + /**
1.978 + * {@inheritDoc}
1.979 + *
1.980 + * <p>The returned iterator provides a snapshot of the state of the list
1.981 + * when the iterator was constructed. No synchronization is needed while
1.982 + * traversing the iterator. The iterator does <em>NOT</em> support the
1.983 + * <tt>remove</tt>, <tt>set</tt> or <tt>add</tt> methods.
1.984 + *
1.985 + * @throws IndexOutOfBoundsException {@inheritDoc}
1.986 + */
1.987 + public ListIterator<E> listIterator(final int index) {
1.988 + Object[] elements = getArray();
1.989 + int len = elements.length;
1.990 + if (index<0 || index>len)
1.991 + throw new IndexOutOfBoundsException("Index: "+index);
1.992 +
1.993 + return new COWIterator<E>(elements, index);
1.994 + }
1.995 +
1.996 + private static class COWIterator<E> implements ListIterator<E> {
1.997 + /** Snapshot of the array */
1.998 + private final Object[] snapshot;
1.999 + /** Index of element to be returned by subsequent call to next. */
1.1000 + private int cursor;
1.1001 +
1.1002 + private COWIterator(Object[] elements, int initialCursor) {
1.1003 + cursor = initialCursor;
1.1004 + snapshot = elements;
1.1005 + }
1.1006 +
1.1007 + public boolean hasNext() {
1.1008 + return cursor < snapshot.length;
1.1009 + }
1.1010 +
1.1011 + public boolean hasPrevious() {
1.1012 + return cursor > 0;
1.1013 + }
1.1014 +
1.1015 + @SuppressWarnings("unchecked")
1.1016 + public E next() {
1.1017 + if (! hasNext())
1.1018 + throw new NoSuchElementException();
1.1019 + return (E) snapshot[cursor++];
1.1020 + }
1.1021 +
1.1022 + @SuppressWarnings("unchecked")
1.1023 + public E previous() {
1.1024 + if (! hasPrevious())
1.1025 + throw new NoSuchElementException();
1.1026 + return (E) snapshot[--cursor];
1.1027 + }
1.1028 +
1.1029 + public int nextIndex() {
1.1030 + return cursor;
1.1031 + }
1.1032 +
1.1033 + public int previousIndex() {
1.1034 + return cursor-1;
1.1035 + }
1.1036 +
1.1037 + /**
1.1038 + * Not supported. Always throws UnsupportedOperationException.
1.1039 + * @throws UnsupportedOperationException always; <tt>remove</tt>
1.1040 + * is not supported by this iterator.
1.1041 + */
1.1042 + public void remove() {
1.1043 + throw new UnsupportedOperationException();
1.1044 + }
1.1045 +
1.1046 + /**
1.1047 + * Not supported. Always throws UnsupportedOperationException.
1.1048 + * @throws UnsupportedOperationException always; <tt>set</tt>
1.1049 + * is not supported by this iterator.
1.1050 + */
1.1051 + public void set(E e) {
1.1052 + throw new UnsupportedOperationException();
1.1053 + }
1.1054 +
1.1055 + /**
1.1056 + * Not supported. Always throws UnsupportedOperationException.
1.1057 + * @throws UnsupportedOperationException always; <tt>add</tt>
1.1058 + * is not supported by this iterator.
1.1059 + */
1.1060 + public void add(E e) {
1.1061 + throw new UnsupportedOperationException();
1.1062 + }
1.1063 + }
1.1064 +
1.1065 + /**
1.1066 + * Returns a view of the portion of this list between
1.1067 + * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
1.1068 + * The returned list is backed by this list, so changes in the
1.1069 + * returned list are reflected in this list.
1.1070 + *
1.1071 + * <p>The semantics of the list returned by this method become
1.1072 + * undefined if the backing list (i.e., this list) is modified in
1.1073 + * any way other than via the returned list.
1.1074 + *
1.1075 + * @param fromIndex low endpoint (inclusive) of the subList
1.1076 + * @param toIndex high endpoint (exclusive) of the subList
1.1077 + * @return a view of the specified range within this list
1.1078 + * @throws IndexOutOfBoundsException {@inheritDoc}
1.1079 + */
1.1080 + public List<E> subList(int fromIndex, int toIndex) {
1.1081 + final ReentrantLock lock = this.lock;
1.1082 + lock.lock();
1.1083 + try {
1.1084 + Object[] elements = getArray();
1.1085 + int len = elements.length;
1.1086 + if (fromIndex < 0 || toIndex > len || fromIndex > toIndex)
1.1087 + throw new IndexOutOfBoundsException();
1.1088 + return new COWSubList<E>(this, fromIndex, toIndex);
1.1089 + } finally {
1.1090 + lock.unlock();
1.1091 + }
1.1092 + }
1.1093 +
1.1094 + /**
1.1095 + * Sublist for CopyOnWriteArrayList.
1.1096 + * This class extends AbstractList merely for convenience, to
1.1097 + * avoid having to define addAll, etc. This doesn't hurt, but
1.1098 + * is wasteful. This class does not need or use modCount
1.1099 + * mechanics in AbstractList, but does need to check for
1.1100 + * concurrent modification using similar mechanics. On each
1.1101 + * operation, the array that we expect the backing list to use
1.1102 + * is checked and updated. Since we do this for all of the
1.1103 + * base operations invoked by those defined in AbstractList,
1.1104 + * all is well. While inefficient, this is not worth
1.1105 + * improving. The kinds of list operations inherited from
1.1106 + * AbstractList are already so slow on COW sublists that
1.1107 + * adding a bit more space/time doesn't seem even noticeable.
1.1108 + */
1.1109 + private static class COWSubList<E>
1.1110 + extends AbstractList<E>
1.1111 + implements RandomAccess
1.1112 + {
1.1113 + private final CopyOnWriteArrayList<E> l;
1.1114 + private final int offset;
1.1115 + private int size;
1.1116 + private Object[] expectedArray;
1.1117 +
1.1118 + // only call this holding l's lock
1.1119 + COWSubList(CopyOnWriteArrayList<E> list,
1.1120 + int fromIndex, int toIndex) {
1.1121 + l = list;
1.1122 + expectedArray = l.getArray();
1.1123 + offset = fromIndex;
1.1124 + size = toIndex - fromIndex;
1.1125 + }
1.1126 +
1.1127 + // only call this holding l's lock
1.1128 + private void checkForComodification() {
1.1129 + if (l.getArray() != expectedArray)
1.1130 + throw new ConcurrentModificationException();
1.1131 + }
1.1132 +
1.1133 + // only call this holding l's lock
1.1134 + private void rangeCheck(int index) {
1.1135 + if (index<0 || index>=size)
1.1136 + throw new IndexOutOfBoundsException("Index: "+index+
1.1137 + ",Size: "+size);
1.1138 + }
1.1139 +
1.1140 + public E set(int index, E element) {
1.1141 + final ReentrantLock lock = l.lock;
1.1142 + lock.lock();
1.1143 + try {
1.1144 + rangeCheck(index);
1.1145 + checkForComodification();
1.1146 + E x = l.set(index+offset, element);
1.1147 + expectedArray = l.getArray();
1.1148 + return x;
1.1149 + } finally {
1.1150 + lock.unlock();
1.1151 + }
1.1152 + }
1.1153 +
1.1154 + public E get(int index) {
1.1155 + final ReentrantLock lock = l.lock;
1.1156 + lock.lock();
1.1157 + try {
1.1158 + rangeCheck(index);
1.1159 + checkForComodification();
1.1160 + return l.get(index+offset);
1.1161 + } finally {
1.1162 + lock.unlock();
1.1163 + }
1.1164 + }
1.1165 +
1.1166 + public int size() {
1.1167 + final ReentrantLock lock = l.lock;
1.1168 + lock.lock();
1.1169 + try {
1.1170 + checkForComodification();
1.1171 + return size;
1.1172 + } finally {
1.1173 + lock.unlock();
1.1174 + }
1.1175 + }
1.1176 +
1.1177 + public void add(int index, E element) {
1.1178 + final ReentrantLock lock = l.lock;
1.1179 + lock.lock();
1.1180 + try {
1.1181 + checkForComodification();
1.1182 + if (index<0 || index>size)
1.1183 + throw new IndexOutOfBoundsException();
1.1184 + l.add(index+offset, element);
1.1185 + expectedArray = l.getArray();
1.1186 + size++;
1.1187 + } finally {
1.1188 + lock.unlock();
1.1189 + }
1.1190 + }
1.1191 +
1.1192 + public void clear() {
1.1193 + final ReentrantLock lock = l.lock;
1.1194 + lock.lock();
1.1195 + try {
1.1196 + checkForComodification();
1.1197 + l.removeRange(offset, offset+size);
1.1198 + expectedArray = l.getArray();
1.1199 + size = 0;
1.1200 + } finally {
1.1201 + lock.unlock();
1.1202 + }
1.1203 + }
1.1204 +
1.1205 + public E remove(int index) {
1.1206 + final ReentrantLock lock = l.lock;
1.1207 + lock.lock();
1.1208 + try {
1.1209 + rangeCheck(index);
1.1210 + checkForComodification();
1.1211 + E result = l.remove(index+offset);
1.1212 + expectedArray = l.getArray();
1.1213 + size--;
1.1214 + return result;
1.1215 + } finally {
1.1216 + lock.unlock();
1.1217 + }
1.1218 + }
1.1219 +
1.1220 + public boolean remove(Object o) {
1.1221 + int index = indexOf(o);
1.1222 + if (index == -1)
1.1223 + return false;
1.1224 + remove(index);
1.1225 + return true;
1.1226 + }
1.1227 +
1.1228 + public Iterator<E> iterator() {
1.1229 + final ReentrantLock lock = l.lock;
1.1230 + lock.lock();
1.1231 + try {
1.1232 + checkForComodification();
1.1233 + return new COWSubListIterator<E>(l, 0, offset, size);
1.1234 + } finally {
1.1235 + lock.unlock();
1.1236 + }
1.1237 + }
1.1238 +
1.1239 + public ListIterator<E> listIterator(final int index) {
1.1240 + final ReentrantLock lock = l.lock;
1.1241 + lock.lock();
1.1242 + try {
1.1243 + checkForComodification();
1.1244 + if (index<0 || index>size)
1.1245 + throw new IndexOutOfBoundsException("Index: "+index+
1.1246 + ", Size: "+size);
1.1247 + return new COWSubListIterator<E>(l, index, offset, size);
1.1248 + } finally {
1.1249 + lock.unlock();
1.1250 + }
1.1251 + }
1.1252 +
1.1253 + public List<E> subList(int fromIndex, int toIndex) {
1.1254 + final ReentrantLock lock = l.lock;
1.1255 + lock.lock();
1.1256 + try {
1.1257 + checkForComodification();
1.1258 + if (fromIndex<0 || toIndex>size)
1.1259 + throw new IndexOutOfBoundsException();
1.1260 + return new COWSubList<E>(l, fromIndex + offset,
1.1261 + toIndex + offset);
1.1262 + } finally {
1.1263 + lock.unlock();
1.1264 + }
1.1265 + }
1.1266 +
1.1267 + }
1.1268 +
1.1269 +
1.1270 + private static class COWSubListIterator<E> implements ListIterator<E> {
1.1271 + private final ListIterator<E> i;
1.1272 + private final int index;
1.1273 + private final int offset;
1.1274 + private final int size;
1.1275 +
1.1276 + COWSubListIterator(List<E> l, int index, int offset,
1.1277 + int size) {
1.1278 + this.index = index;
1.1279 + this.offset = offset;
1.1280 + this.size = size;
1.1281 + i = l.listIterator(index+offset);
1.1282 + }
1.1283 +
1.1284 + public boolean hasNext() {
1.1285 + return nextIndex() < size;
1.1286 + }
1.1287 +
1.1288 + public E next() {
1.1289 + if (hasNext())
1.1290 + return i.next();
1.1291 + else
1.1292 + throw new NoSuchElementException();
1.1293 + }
1.1294 +
1.1295 + public boolean hasPrevious() {
1.1296 + return previousIndex() >= 0;
1.1297 + }
1.1298 +
1.1299 + public E previous() {
1.1300 + if (hasPrevious())
1.1301 + return i.previous();
1.1302 + else
1.1303 + throw new NoSuchElementException();
1.1304 + }
1.1305 +
1.1306 + public int nextIndex() {
1.1307 + return i.nextIndex() - offset;
1.1308 + }
1.1309 +
1.1310 + public int previousIndex() {
1.1311 + return i.previousIndex() - offset;
1.1312 + }
1.1313 +
1.1314 + public void remove() {
1.1315 + throw new UnsupportedOperationException();
1.1316 + }
1.1317 +
1.1318 + public void set(E e) {
1.1319 + throw new UnsupportedOperationException();
1.1320 + }
1.1321 +
1.1322 + public void add(E e) {
1.1323 + throw new UnsupportedOperationException();
1.1324 + }
1.1325 + }
1.1326 +
1.1327 + // Support for resetting lock while deserializing
1.1328 + private void resetLock() {
1.1329 + UNSAFE.putObjectVolatile(this, lockOffset, new ReentrantLock());
1.1330 + }
1.1331 + private static final sun.misc.Unsafe UNSAFE;
1.1332 + private static final long lockOffset;
1.1333 + static {
1.1334 + try {
1.1335 + UNSAFE = sun.misc.Unsafe.getUnsafe();
1.1336 + Class k = CopyOnWriteArrayList.class;
1.1337 + lockOffset = UNSAFE.objectFieldOffset
1.1338 + (k.getDeclaredField("lock"));
1.1339 + } catch (Exception e) {
1.1340 + throw new Error(e);
1.1341 + }
1.1342 + }
1.1343 +}