1 /* 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 3 * 4 * This code is free software; you can redistribute it and/or modify it 5 * under the terms of the GNU General Public License version 2 only, as 6 * published by the Free Software Foundation. Oracle designates this 7 * particular file as subject to the "Classpath" exception as provided 8 * by Oracle in the LICENSE file that accompanied this code. 9 * 10 * This code is distributed in the hope that it will be useful, but WITHOUT 11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 13 * version 2 for more details (a copy is included in the LICENSE file that 14 * accompanied this code). 15 * 16 * You should have received a copy of the GNU General Public License version 17 * 2 along with this work; if not, write to the Free Software Foundation, 18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 19 * 20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 21 * or visit www.oracle.com if you need additional information or have any 22 * questions. 23 */ 24 25 /* 26 * Written by Doug Lea with assistance from members of JCP JSR-166 27 * Expert Group. Adapted and released, under explicit permission, 28 * from JDK ArrayList.java which carries the following copyright: 29 * 30 * Copyright 1997 by Sun Microsystems, Inc., 31 * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A. 32 * All rights reserved. 33 */ 34 35 package java.util.concurrent; 36 37 import java.lang.invoke.VarHandle; 38 import java.lang.reflect.Field; 39 import java.util.ArrayList; 40 import java.util.Arrays; 41 import java.util.Collection; 42 import java.util.Comparator; 43 import java.util.ConcurrentModificationException; 44 import java.util.Iterator; 45 import java.util.List; 46 import java.util.ListIterator; 47 import java.util.NoSuchElementException; 48 import java.util.Objects; 49 import java.util.RandomAccess; 50 import java.util.Spliterator; 51 import java.util.Spliterators; 52 import java.util.function.Consumer; 53 import java.util.function.Predicate; 54 import java.util.function.UnaryOperator; 55 import jdk.internal.access.SharedSecrets; 56 57 /** 58 * A thread-safe variant of {@link java.util.ArrayList} in which all mutative 59 * operations ({@code add}, {@code set}, and so on) are implemented by 60 * making a fresh copy of the underlying array. 61 * 62 * <p>This is ordinarily too costly, but may be <em>more</em> efficient 63 * than alternatives when traversal operations vastly outnumber 64 * mutations, and is useful when you cannot or don't want to 65 * synchronize traversals, yet need to preclude interference among 66 * concurrent threads. The "snapshot" style iterator method uses a 67 * reference to the state of the array at the point that the iterator 68 * was created. This array never changes during the lifetime of the 69 * iterator, so interference is impossible and the iterator is 70 * guaranteed not to throw {@code ConcurrentModificationException}. 71 * The iterator will not reflect additions, removals, or changes to 72 * the list since the iterator was created. Element-changing 73 * operations on iterators themselves ({@code remove}, {@code set}, and 74 * {@code add}) are not supported. These methods throw 75 * {@code UnsupportedOperationException}. 76 * 77 * <p>All elements are permitted, including {@code null}. 78 * 79 * <p>Memory consistency effects: As with other concurrent 80 * collections, actions in a thread prior to placing an object into a 81 * {@code CopyOnWriteArrayList} 82 * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a> 83 * actions subsequent to the access or removal of that element from 84 * the {@code CopyOnWriteArrayList} in another thread. 85 * 86 * <p>This class is a member of the 87 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework"> 88 * Java Collections Framework</a>. 89 * 90 * @since 1.5 91 * @author Doug Lea 92 * @param <E> the type of elements held in this list 93 */ 94 public class CopyOnWriteArrayList<E> 95 implements List<E>, RandomAccess, Cloneable, java.io.Serializable { 96 private static final long serialVersionUID = 8673264195747942595L; 97 98 /** 99 * The lock protecting all mutators. (We have a mild preference 100 * for builtin monitors over ReentrantLock when either will do.) 101 */ 102 final transient Object lock = new Object(); 103 104 /** The array, accessed only via getArray/setArray. */ 105 private transient volatile Object[] array; 106 107 /** 108 * Gets the array. Non-private so as to also be accessible 109 * from CopyOnWriteArraySet class. 110 */ getArray()111 final Object[] getArray() { 112 return array; 113 } 114 115 /** 116 * Sets the array. 117 */ setArray(Object[] a)118 final void setArray(Object[] a) { 119 array = a; 120 } 121 122 /** 123 * Creates an empty list. 124 */ CopyOnWriteArrayList()125 public CopyOnWriteArrayList() { 126 setArray(new Object[0]); 127 } 128 129 /** 130 * Creates a list containing the elements of the specified 131 * collection, in the order they are returned by the collection's 132 * iterator. 133 * 134 * @param c the collection of initially held elements 135 * @throws NullPointerException if the specified collection is null 136 */ CopyOnWriteArrayList(Collection<? extends E> c)137 public CopyOnWriteArrayList(Collection<? extends E> c) { 138 Object[] es; 139 if (c.getClass() == CopyOnWriteArrayList.class) 140 es = ((CopyOnWriteArrayList<?>)c).getArray(); 141 else { 142 es = c.toArray(); 143 if (c.getClass() != java.util.ArrayList.class) 144 es = Arrays.copyOf(es, es.length, Object[].class); 145 } 146 setArray(es); 147 } 148 149 /** 150 * Creates a list holding a copy of the given array. 151 * 152 * @param toCopyIn the array (a copy of this array is used as the 153 * internal array) 154 * @throws NullPointerException if the specified array is null 155 */ CopyOnWriteArrayList(E[] toCopyIn)156 public CopyOnWriteArrayList(E[] toCopyIn) { 157 setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class)); 158 } 159 160 /** 161 * Returns the number of elements in this list. 162 * 163 * @return the number of elements in this list 164 */ size()165 public int size() { 166 return getArray().length; 167 } 168 169 /** 170 * Returns {@code true} if this list contains no elements. 171 * 172 * @return {@code true} if this list contains no elements 173 */ isEmpty()174 public boolean isEmpty() { 175 return size() == 0; 176 } 177 178 /** 179 * static version of indexOf, to allow repeated calls without 180 * needing to re-acquire array each time. 181 * @param o element to search for 182 * @param es the array 183 * @param from first index to search 184 * @param to one past last index to search 185 * @return index of element, or -1 if absent 186 */ indexOfRange(Object o, Object[] es, int from, int to)187 private static int indexOfRange(Object o, Object[] es, int from, int to) { 188 if (o == null) { 189 for (int i = from; i < to; i++) 190 if (es[i] == null) 191 return i; 192 } else { 193 for (int i = from; i < to; i++) 194 if (o.equals(es[i])) 195 return i; 196 } 197 return -1; 198 } 199 200 /** 201 * static version of lastIndexOf. 202 * @param o element to search for 203 * @param es the array 204 * @param from index of first element of range, last element to search 205 * @param to one past last element of range, first element to search 206 * @return index of element, or -1 if absent 207 */ lastIndexOfRange(Object o, Object[] es, int from, int to)208 private static int lastIndexOfRange(Object o, Object[] es, int from, int to) { 209 if (o == null) { 210 for (int i = to - 1; i >= from; i--) 211 if (es[i] == null) 212 return i; 213 } else { 214 for (int i = to - 1; i >= from; i--) 215 if (o.equals(es[i])) 216 return i; 217 } 218 return -1; 219 } 220 221 /** 222 * Returns {@code true} if this list contains the specified element. 223 * More formally, returns {@code true} if and only if this list contains 224 * at least one element {@code e} such that {@code Objects.equals(o, e)}. 225 * 226 * @param o element whose presence in this list is to be tested 227 * @return {@code true} if this list contains the specified element 228 */ contains(Object o)229 public boolean contains(Object o) { 230 return indexOf(o) >= 0; 231 } 232 233 /** 234 * {@inheritDoc} 235 */ indexOf(Object o)236 public int indexOf(Object o) { 237 Object[] es = getArray(); 238 return indexOfRange(o, es, 0, es.length); 239 } 240 241 /** 242 * Returns the index of the first occurrence of the specified element in 243 * this list, searching forwards from {@code index}, or returns -1 if 244 * the element is not found. 245 * More formally, returns the lowest index {@code i} such that 246 * {@code i >= index && Objects.equals(get(i), e)}, 247 * or -1 if there is no such index. 248 * 249 * @param e element to search for 250 * @param index index to start searching from 251 * @return the index of the first occurrence of the element in 252 * this list at position {@code index} or later in the list; 253 * {@code -1} if the element is not found. 254 * @throws IndexOutOfBoundsException if the specified index is negative 255 */ indexOf(E e, int index)256 public int indexOf(E e, int index) { 257 Object[] es = getArray(); 258 return indexOfRange(e, es, index, es.length); 259 } 260 261 /** 262 * {@inheritDoc} 263 */ lastIndexOf(Object o)264 public int lastIndexOf(Object o) { 265 Object[] es = getArray(); 266 return lastIndexOfRange(o, es, 0, es.length); 267 } 268 269 /** 270 * Returns the index of the last occurrence of the specified element in 271 * this list, searching backwards from {@code index}, or returns -1 if 272 * the element is not found. 273 * More formally, returns the highest index {@code i} such that 274 * {@code i <= index && Objects.equals(get(i), e)}, 275 * or -1 if there is no such index. 276 * 277 * @param e element to search for 278 * @param index index to start searching backwards from 279 * @return the index of the last occurrence of the element at position 280 * less than or equal to {@code index} in this list; 281 * -1 if the element is not found. 282 * @throws IndexOutOfBoundsException if the specified index is greater 283 * than or equal to the current size of this list 284 */ lastIndexOf(E e, int index)285 public int lastIndexOf(E e, int index) { 286 Object[] es = getArray(); 287 return lastIndexOfRange(e, es, 0, index + 1); 288 } 289 290 /** 291 * Returns a shallow copy of this list. (The elements themselves 292 * are not copied.) 293 * 294 * @return a clone of this list 295 */ clone()296 public Object clone() { 297 try { 298 @SuppressWarnings("unchecked") 299 CopyOnWriteArrayList<E> clone = 300 (CopyOnWriteArrayList<E>) super.clone(); 301 clone.resetLock(); 302 // Unlike in readObject, here we cannot visibility-piggyback on the 303 // volatile write in setArray(). 304 VarHandle.releaseFence(); 305 return clone; 306 } catch (CloneNotSupportedException e) { 307 // this shouldn't happen, since we are Cloneable 308 throw new InternalError(); 309 } 310 } 311 312 /** 313 * Returns an array containing all of the elements in this list 314 * in proper sequence (from first to last element). 315 * 316 * <p>The returned array will be "safe" in that no references to it are 317 * maintained by this list. (In other words, this method must allocate 318 * a new array). The caller is thus free to modify the returned array. 319 * 320 * <p>This method acts as bridge between array-based and collection-based 321 * APIs. 322 * 323 * @return an array containing all the elements in this list 324 */ toArray()325 public Object[] toArray() { 326 return getArray().clone(); 327 } 328 329 /** 330 * Returns an array containing all of the elements in this list in 331 * proper sequence (from first to last element); the runtime type of 332 * the returned array is that of the specified array. If the list fits 333 * in the specified array, it is returned therein. Otherwise, a new 334 * array is allocated with the runtime type of the specified array and 335 * the size of this list. 336 * 337 * <p>If this list fits in the specified array with room to spare 338 * (i.e., the array has more elements than this list), the element in 339 * the array immediately following the end of the list is set to 340 * {@code null}. (This is useful in determining the length of this 341 * list <i>only</i> if the caller knows that this list does not contain 342 * any null elements.) 343 * 344 * <p>Like the {@link #toArray()} method, this method acts as bridge between 345 * array-based and collection-based APIs. Further, this method allows 346 * precise control over the runtime type of the output array, and may, 347 * under certain circumstances, be used to save allocation costs. 348 * 349 * <p>Suppose {@code x} is a list known to contain only strings. 350 * The following code can be used to dump the list into a newly 351 * allocated array of {@code String}: 352 * 353 * <pre> {@code String[] y = x.toArray(new String[0]);}</pre> 354 * 355 * Note that {@code toArray(new Object[0])} is identical in function to 356 * {@code toArray()}. 357 * 358 * @param a the array into which the elements of the list are to 359 * be stored, if it is big enough; otherwise, a new array of the 360 * same runtime type is allocated for this purpose. 361 * @return an array containing all the elements in this list 362 * @throws ArrayStoreException if the runtime type of the specified array 363 * is not a supertype of the runtime type of every element in 364 * this list 365 * @throws NullPointerException if the specified array is null 366 */ 367 @SuppressWarnings("unchecked") toArray(T[] a)368 public <T> T[] toArray(T[] a) { 369 Object[] es = getArray(); 370 int len = es.length; 371 if (a.length < len) 372 return (T[]) Arrays.copyOf(es, len, a.getClass()); 373 else { 374 System.arraycopy(es, 0, a, 0, len); 375 if (a.length > len) 376 a[len] = null; 377 return a; 378 } 379 } 380 381 // Positional Access Operations 382 383 @SuppressWarnings("unchecked") elementAt(Object[] a, int index)384 static <E> E elementAt(Object[] a, int index) { 385 return (E) a[index]; 386 } 387 outOfBounds(int index, int size)388 static String outOfBounds(int index, int size) { 389 return "Index: " + index + ", Size: " + size; 390 } 391 392 /** 393 * {@inheritDoc} 394 * 395 * @throws IndexOutOfBoundsException {@inheritDoc} 396 */ get(int index)397 public E get(int index) { 398 return elementAt(getArray(), index); 399 } 400 401 /** 402 * Replaces the element at the specified position in this list with the 403 * specified element. 404 * 405 * @throws IndexOutOfBoundsException {@inheritDoc} 406 */ set(int index, E element)407 public E set(int index, E element) { 408 synchronized (lock) { 409 Object[] es = getArray(); 410 E oldValue = elementAt(es, index); 411 412 if (oldValue != element) { 413 es = es.clone(); 414 es[index] = element; 415 } 416 // Ensure volatile write semantics even when oldvalue == element 417 setArray(es); 418 return oldValue; 419 } 420 } 421 422 /** 423 * Appends the specified element to the end of this list. 424 * 425 * @param e element to be appended to this list 426 * @return {@code true} (as specified by {@link Collection#add}) 427 */ add(E e)428 public boolean add(E e) { 429 synchronized (lock) { 430 Object[] es = getArray(); 431 int len = es.length; 432 es = Arrays.copyOf(es, len + 1); 433 es[len] = e; 434 setArray(es); 435 return true; 436 } 437 } 438 439 /** 440 * Inserts the specified element at the specified position in this 441 * list. Shifts the element currently at that position (if any) and 442 * any subsequent elements to the right (adds one to their indices). 443 * 444 * @throws IndexOutOfBoundsException {@inheritDoc} 445 */ add(int index, E element)446 public void add(int index, E element) { 447 synchronized (lock) { 448 Object[] es = getArray(); 449 int len = es.length; 450 if (index > len || index < 0) 451 throw new IndexOutOfBoundsException(outOfBounds(index, len)); 452 Object[] newElements; 453 int numMoved = len - index; 454 if (numMoved == 0) 455 newElements = Arrays.copyOf(es, len + 1); 456 else { 457 newElements = new Object[len + 1]; 458 System.arraycopy(es, 0, newElements, 0, index); 459 System.arraycopy(es, index, newElements, index + 1, 460 numMoved); 461 } 462 newElements[index] = element; 463 setArray(newElements); 464 } 465 } 466 467 /** 468 * Removes the element at the specified position in this list. 469 * Shifts any subsequent elements to the left (subtracts one from their 470 * indices). Returns the element that was removed from the list. 471 * 472 * @throws IndexOutOfBoundsException {@inheritDoc} 473 */ remove(int index)474 public E remove(int index) { 475 synchronized (lock) { 476 Object[] es = getArray(); 477 int len = es.length; 478 E oldValue = elementAt(es, index); 479 int numMoved = len - index - 1; 480 Object[] newElements; 481 if (numMoved == 0) 482 newElements = Arrays.copyOf(es, len - 1); 483 else { 484 newElements = new Object[len - 1]; 485 System.arraycopy(es, 0, newElements, 0, index); 486 System.arraycopy(es, index + 1, newElements, index, 487 numMoved); 488 } 489 setArray(newElements); 490 return oldValue; 491 } 492 } 493 494 /** 495 * Removes the first occurrence of the specified element from this list, 496 * if it is present. If this list does not contain the element, it is 497 * unchanged. More formally, removes the element with the lowest index 498 * {@code i} such that {@code Objects.equals(o, get(i))} 499 * (if such an element exists). Returns {@code true} if this list 500 * contained the specified element (or equivalently, if this list 501 * changed as a result of the call). 502 * 503 * @param o element to be removed from this list, if present 504 * @return {@code true} if this list contained the specified element 505 */ remove(Object o)506 public boolean remove(Object o) { 507 Object[] snapshot = getArray(); 508 int index = indexOfRange(o, snapshot, 0, snapshot.length); 509 return index >= 0 && remove(o, snapshot, index); 510 } 511 512 /** 513 * A version of remove(Object) using the strong hint that given 514 * recent snapshot contains o at the given index. 515 */ remove(Object o, Object[] snapshot, int index)516 private boolean remove(Object o, Object[] snapshot, int index) { 517 synchronized (lock) { 518 Object[] current = getArray(); 519 int len = current.length; 520 if (snapshot != current) findIndex: { 521 int prefix = Math.min(index, len); 522 for (int i = 0; i < prefix; i++) { 523 if (current[i] != snapshot[i] 524 && Objects.equals(o, current[i])) { 525 index = i; 526 break findIndex; 527 } 528 } 529 if (index >= len) 530 return false; 531 if (current[index] == o) 532 break findIndex; 533 index = indexOfRange(o, current, index, len); 534 if (index < 0) 535 return false; 536 } 537 Object[] newElements = new Object[len - 1]; 538 System.arraycopy(current, 0, newElements, 0, index); 539 System.arraycopy(current, index + 1, 540 newElements, index, 541 len - index - 1); 542 setArray(newElements); 543 return true; 544 } 545 } 546 547 /** 548 * Removes from this list all of the elements whose index is between 549 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. 550 * Shifts any succeeding elements to the left (reduces their index). 551 * This call shortens the list by {@code (toIndex - fromIndex)} elements. 552 * (If {@code toIndex==fromIndex}, this operation has no effect.) 553 * 554 * @param fromIndex index of first element to be removed 555 * @param toIndex index after last element to be removed 556 * @throws IndexOutOfBoundsException if fromIndex or toIndex out of range 557 * ({@code fromIndex < 0 || toIndex > size() || toIndex < fromIndex}) 558 */ removeRange(int fromIndex, int toIndex)559 void removeRange(int fromIndex, int toIndex) { 560 synchronized (lock) { 561 Object[] es = getArray(); 562 int len = es.length; 563 564 if (fromIndex < 0 || toIndex > len || toIndex < fromIndex) 565 throw new IndexOutOfBoundsException(); 566 int newlen = len - (toIndex - fromIndex); 567 int numMoved = len - toIndex; 568 if (numMoved == 0) 569 setArray(Arrays.copyOf(es, newlen)); 570 else { 571 Object[] newElements = new Object[newlen]; 572 System.arraycopy(es, 0, newElements, 0, fromIndex); 573 System.arraycopy(es, toIndex, newElements, 574 fromIndex, numMoved); 575 setArray(newElements); 576 } 577 } 578 } 579 580 /** 581 * Appends the element, if not present. 582 * 583 * @param e element to be added to this list, if absent 584 * @return {@code true} if the element was added 585 */ addIfAbsent(E e)586 public boolean addIfAbsent(E e) { 587 Object[] snapshot = getArray(); 588 return indexOfRange(e, snapshot, 0, snapshot.length) < 0 589 && addIfAbsent(e, snapshot); 590 } 591 592 /** 593 * A version of addIfAbsent using the strong hint that given 594 * recent snapshot does not contain e. 595 */ addIfAbsent(E e, Object[] snapshot)596 private boolean addIfAbsent(E e, Object[] snapshot) { 597 synchronized (lock) { 598 Object[] current = getArray(); 599 int len = current.length; 600 if (snapshot != current) { 601 // Optimize for lost race to another addXXX operation 602 int common = Math.min(snapshot.length, len); 603 for (int i = 0; i < common; i++) 604 if (current[i] != snapshot[i] 605 && Objects.equals(e, current[i])) 606 return false; 607 if (indexOfRange(e, current, common, len) >= 0) 608 return false; 609 } 610 Object[] newElements = Arrays.copyOf(current, len + 1); 611 newElements[len] = e; 612 setArray(newElements); 613 return true; 614 } 615 } 616 617 /** 618 * Returns {@code true} if this list contains all of the elements of the 619 * specified collection. 620 * 621 * @param c collection to be checked for containment in this list 622 * @return {@code true} if this list contains all of the elements of the 623 * specified collection 624 * @throws NullPointerException if the specified collection is null 625 * @see #contains(Object) 626 */ containsAll(Collection<?> c)627 public boolean containsAll(Collection<?> c) { 628 Object[] es = getArray(); 629 int len = es.length; 630 for (Object e : c) { 631 if (indexOfRange(e, es, 0, len) < 0) 632 return false; 633 } 634 return true; 635 } 636 637 /** 638 * Removes from this list all of its elements that are contained in 639 * the specified collection. This is a particularly expensive operation 640 * in this class because of the need for an internal temporary array. 641 * 642 * @param c collection containing elements to be removed from this list 643 * @return {@code true} if this list changed as a result of the call 644 * @throws ClassCastException if the class of an element of this list 645 * is incompatible with the specified collection 646 * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>) 647 * @throws NullPointerException if this list contains a null element and the 648 * specified collection does not permit null elements 649 * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>), 650 * or if the specified collection is null 651 * @see #remove(Object) 652 */ removeAll(Collection<?> c)653 public boolean removeAll(Collection<?> c) { 654 Objects.requireNonNull(c); 655 return bulkRemove(e -> c.contains(e)); 656 } 657 658 /** 659 * Retains only the elements in this list that are contained in the 660 * specified collection. In other words, removes from this list all of 661 * its elements that are not contained in the specified collection. 662 * 663 * @param c collection containing elements to be retained in this list 664 * @return {@code true} if this list changed as a result of the call 665 * @throws ClassCastException if the class of an element of this list 666 * is incompatible with the specified collection 667 * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>) 668 * @throws NullPointerException if this list contains a null element and the 669 * specified collection does not permit null elements 670 * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>), 671 * or if the specified collection is null 672 * @see #remove(Object) 673 */ retainAll(Collection<?> c)674 public boolean retainAll(Collection<?> c) { 675 Objects.requireNonNull(c); 676 return bulkRemove(e -> !c.contains(e)); 677 } 678 679 /** 680 * Appends all of the elements in the specified collection that 681 * are not already contained in this list, to the end of 682 * this list, in the order that they are returned by the 683 * specified collection's iterator. 684 * 685 * @param c collection containing elements to be added to this list 686 * @return the number of elements added 687 * @throws NullPointerException if the specified collection is null 688 * @see #addIfAbsent(Object) 689 */ addAllAbsent(Collection<? extends E> c)690 public int addAllAbsent(Collection<? extends E> c) { 691 Object[] cs = c.toArray(); 692 if (c.getClass() != ArrayList.class) { 693 cs = cs.clone(); 694 } 695 if (cs.length == 0) 696 return 0; 697 synchronized (lock) { 698 Object[] es = getArray(); 699 int len = es.length; 700 int added = 0; 701 // uniquify and compact elements in cs 702 for (int i = 0; i < cs.length; ++i) { 703 Object e = cs[i]; 704 if (indexOfRange(e, es, 0, len) < 0 && 705 indexOfRange(e, cs, 0, added) < 0) 706 cs[added++] = e; 707 } 708 if (added > 0) { 709 Object[] newElements = Arrays.copyOf(es, len + added); 710 System.arraycopy(cs, 0, newElements, len, added); 711 setArray(newElements); 712 } 713 return added; 714 } 715 } 716 717 /** 718 * Removes all of the elements from this list. 719 * The list will be empty after this call returns. 720 */ clear()721 public void clear() { 722 synchronized (lock) { 723 setArray(new Object[0]); 724 } 725 } 726 727 /** 728 * Appends all of the elements in the specified collection to the end 729 * of this list, in the order that they are returned by the specified 730 * collection's iterator. 731 * 732 * @param c collection containing elements to be added to this list 733 * @return {@code true} if this list changed as a result of the call 734 * @throws NullPointerException if the specified collection is null 735 * @see #add(Object) 736 */ addAll(Collection<? extends E> c)737 public boolean addAll(Collection<? extends E> c) { 738 Object[] cs = (c.getClass() == CopyOnWriteArrayList.class) ? 739 ((CopyOnWriteArrayList<?>)c).getArray() : c.toArray(); 740 if (cs.length == 0) 741 return false; 742 synchronized (lock) { 743 Object[] es = getArray(); 744 int len = es.length; 745 Object[] newElements; 746 if (len == 0 && (c.getClass() == CopyOnWriteArrayList.class || 747 c.getClass() == ArrayList.class)) { 748 newElements = cs; 749 } else { 750 newElements = Arrays.copyOf(es, len + cs.length); 751 System.arraycopy(cs, 0, newElements, len, cs.length); 752 } 753 setArray(newElements); 754 return true; 755 } 756 } 757 758 /** 759 * Inserts all of the elements in the specified collection into this 760 * list, starting at the specified position. Shifts the element 761 * currently at that position (if any) and any subsequent elements to 762 * the right (increases their indices). The new elements will appear 763 * in this list in the order that they are returned by the 764 * specified collection's iterator. 765 * 766 * @param index index at which to insert the first element 767 * from the specified collection 768 * @param c collection containing elements to be added to this list 769 * @return {@code true} if this list changed as a result of the call 770 * @throws IndexOutOfBoundsException {@inheritDoc} 771 * @throws NullPointerException if the specified collection is null 772 * @see #add(int,Object) 773 */ addAll(int index, Collection<? extends E> c)774 public boolean addAll(int index, Collection<? extends E> c) { 775 Object[] cs = c.toArray(); 776 synchronized (lock) { 777 Object[] es = getArray(); 778 int len = es.length; 779 if (index > len || index < 0) 780 throw new IndexOutOfBoundsException(outOfBounds(index, len)); 781 if (cs.length == 0) 782 return false; 783 int numMoved = len - index; 784 Object[] newElements; 785 if (numMoved == 0) 786 newElements = Arrays.copyOf(es, len + cs.length); 787 else { 788 newElements = new Object[len + cs.length]; 789 System.arraycopy(es, 0, newElements, 0, index); 790 System.arraycopy(es, index, 791 newElements, index + cs.length, 792 numMoved); 793 } 794 System.arraycopy(cs, 0, newElements, index, cs.length); 795 setArray(newElements); 796 return true; 797 } 798 } 799 800 /** 801 * @throws NullPointerException {@inheritDoc} 802 */ forEach(Consumer<? super E> action)803 public void forEach(Consumer<? super E> action) { 804 Objects.requireNonNull(action); 805 for (Object x : getArray()) { 806 @SuppressWarnings("unchecked") E e = (E) x; 807 action.accept(e); 808 } 809 } 810 811 /** 812 * @throws NullPointerException {@inheritDoc} 813 */ removeIf(Predicate<? super E> filter)814 public boolean removeIf(Predicate<? super E> filter) { 815 Objects.requireNonNull(filter); 816 return bulkRemove(filter); 817 } 818 819 // A tiny bit set implementation 820 nBits(int n)821 private static long[] nBits(int n) { 822 return new long[((n - 1) >> 6) + 1]; 823 } setBit(long[] bits, int i)824 private static void setBit(long[] bits, int i) { 825 bits[i >> 6] |= 1L << i; 826 } isClear(long[] bits, int i)827 private static boolean isClear(long[] bits, int i) { 828 return (bits[i >> 6] & (1L << i)) == 0; 829 } 830 bulkRemove(Predicate<? super E> filter)831 private boolean bulkRemove(Predicate<? super E> filter) { 832 synchronized (lock) { 833 return bulkRemove(filter, 0, getArray().length); 834 } 835 } 836 bulkRemove(Predicate<? super E> filter, int i, int end)837 boolean bulkRemove(Predicate<? super E> filter, int i, int end) { 838 // assert Thread.holdsLock(lock); 839 final Object[] es = getArray(); 840 // Optimize for initial run of survivors 841 for (; i < end && !filter.test(elementAt(es, i)); i++) 842 ; 843 if (i < end) { 844 final int beg = i; 845 final long[] deathRow = nBits(end - beg); 846 int deleted = 1; 847 deathRow[0] = 1L; // set bit 0 848 for (i = beg + 1; i < end; i++) 849 if (filter.test(elementAt(es, i))) { 850 setBit(deathRow, i - beg); 851 deleted++; 852 } 853 // Did filter reentrantly modify the list? 854 if (es != getArray()) 855 throw new ConcurrentModificationException(); 856 final Object[] newElts = Arrays.copyOf(es, es.length - deleted); 857 int w = beg; 858 for (i = beg; i < end; i++) 859 if (isClear(deathRow, i - beg)) 860 newElts[w++] = es[i]; 861 System.arraycopy(es, i, newElts, w, es.length - i); 862 setArray(newElts); 863 return true; 864 } else { 865 if (es != getArray()) 866 throw new ConcurrentModificationException(); 867 return false; 868 } 869 } 870 replaceAll(UnaryOperator<E> operator)871 public void replaceAll(UnaryOperator<E> operator) { 872 synchronized (lock) { 873 replaceAllRange(operator, 0, getArray().length); 874 } 875 } 876 replaceAllRange(UnaryOperator<E> operator, int i, int end)877 void replaceAllRange(UnaryOperator<E> operator, int i, int end) { 878 // assert Thread.holdsLock(lock); 879 Objects.requireNonNull(operator); 880 final Object[] es = getArray().clone(); 881 for (; i < end; i++) 882 es[i] = operator.apply(elementAt(es, i)); 883 setArray(es); 884 } 885 sort(Comparator<? super E> c)886 public void sort(Comparator<? super E> c) { 887 synchronized (lock) { 888 sortRange(c, 0, getArray().length); 889 } 890 } 891 892 @SuppressWarnings("unchecked") sortRange(Comparator<? super E> c, int i, int end)893 void sortRange(Comparator<? super E> c, int i, int end) { 894 // assert Thread.holdsLock(lock); 895 final Object[] es = getArray().clone(); 896 Arrays.sort(es, i, end, (Comparator<Object>)c); 897 setArray(es); 898 } 899 900 /** 901 * Saves this list to a stream (that is, serializes it). 902 * 903 * @param s the stream 904 * @throws java.io.IOException if an I/O error occurs 905 * @serialData The length of the array backing the list is emitted 906 * (int), followed by all of its elements (each an Object) 907 * in the proper order. 908 */ writeObject(java.io.ObjectOutputStream s)909 private void writeObject(java.io.ObjectOutputStream s) 910 throws java.io.IOException { 911 912 s.defaultWriteObject(); 913 914 Object[] es = getArray(); 915 // Write out array length 916 s.writeInt(es.length); 917 918 // Write out all elements in the proper order. 919 for (Object element : es) 920 s.writeObject(element); 921 } 922 923 /** 924 * Reconstitutes this list from a stream (that is, deserializes it). 925 * @param s the stream 926 * @throws ClassNotFoundException if the class of a serialized object 927 * could not be found 928 * @throws java.io.IOException if an I/O error occurs 929 */ readObject(java.io.ObjectInputStream s)930 private void readObject(java.io.ObjectInputStream s) 931 throws java.io.IOException, ClassNotFoundException { 932 933 s.defaultReadObject(); 934 935 // bind to new lock 936 resetLock(); 937 938 // Read in array length and allocate array 939 int len = s.readInt(); 940 SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, len); 941 Object[] es = new Object[len]; 942 943 // Read in all elements in the proper order. 944 for (int i = 0; i < len; i++) 945 es[i] = s.readObject(); 946 setArray(es); 947 } 948 949 /** 950 * Returns a string representation of this list. The string 951 * representation consists of the string representations of the list's 952 * elements in the order they are returned by its iterator, enclosed in 953 * square brackets ({@code "[]"}). Adjacent elements are separated by 954 * the characters {@code ", "} (comma and space). Elements are 955 * converted to strings as by {@link String#valueOf(Object)}. 956 * 957 * @return a string representation of this list 958 */ toString()959 public String toString() { 960 return Arrays.toString(getArray()); 961 } 962 963 /** 964 * Compares the specified object with this list for equality. 965 * Returns {@code true} if the specified object is the same object 966 * as this object, or if it is also a {@link List} and the sequence 967 * of elements returned by an {@linkplain List#iterator() iterator} 968 * over the specified list is the same as the sequence returned by 969 * an iterator over this list. The two sequences are considered to 970 * be the same if they have the same length and corresponding 971 * elements at the same position in the sequence are <em>equal</em>. 972 * Two elements {@code e1} and {@code e2} are considered 973 * <em>equal</em> if {@code Objects.equals(e1, e2)}. 974 * 975 * @param o the object to be compared for equality with this list 976 * @return {@code true} if the specified object is equal to this list 977 */ equals(Object o)978 public boolean equals(Object o) { 979 if (o == this) 980 return true; 981 if (!(o instanceof List)) 982 return false; 983 984 List<?> list = (List<?>)o; 985 Iterator<?> it = list.iterator(); 986 for (Object element : getArray()) 987 if (!it.hasNext() || !Objects.equals(element, it.next())) 988 return false; 989 return !it.hasNext(); 990 } 991 hashCodeOfRange(Object[] es, int from, int to)992 private static int hashCodeOfRange(Object[] es, int from, int to) { 993 int hashCode = 1; 994 for (int i = from; i < to; i++) { 995 Object x = es[i]; 996 hashCode = 31 * hashCode + (x == null ? 0 : x.hashCode()); 997 } 998 return hashCode; 999 } 1000 1001 /** 1002 * Returns the hash code value for this list. 1003 * 1004 * <p>This implementation uses the definition in {@link List#hashCode}. 1005 * 1006 * @return the hash code value for this list 1007 */ hashCode()1008 public int hashCode() { 1009 Object[] es = getArray(); 1010 return hashCodeOfRange(es, 0, es.length); 1011 } 1012 1013 /** 1014 * Returns an iterator over the elements in this list in proper sequence. 1015 * 1016 * <p>The returned iterator provides a snapshot of the state of the list 1017 * when the iterator was constructed. No synchronization is needed while 1018 * traversing the iterator. The iterator does <em>NOT</em> support the 1019 * {@code remove} method. 1020 * 1021 * @return an iterator over the elements in this list in proper sequence 1022 */ iterator()1023 public Iterator<E> iterator() { 1024 return new COWIterator<E>(getArray(), 0); 1025 } 1026 1027 /** 1028 * {@inheritDoc} 1029 * 1030 * <p>The returned iterator provides a snapshot of the state of the list 1031 * when the iterator was constructed. No synchronization is needed while 1032 * traversing the iterator. The iterator does <em>NOT</em> support the 1033 * {@code remove}, {@code set} or {@code add} methods. 1034 */ listIterator()1035 public ListIterator<E> listIterator() { 1036 return new COWIterator<E>(getArray(), 0); 1037 } 1038 1039 /** 1040 * {@inheritDoc} 1041 * 1042 * <p>The returned iterator provides a snapshot of the state of the list 1043 * when the iterator was constructed. No synchronization is needed while 1044 * traversing the iterator. The iterator does <em>NOT</em> support the 1045 * {@code remove}, {@code set} or {@code add} methods. 1046 * 1047 * @throws IndexOutOfBoundsException {@inheritDoc} 1048 */ listIterator(int index)1049 public ListIterator<E> listIterator(int index) { 1050 Object[] es = getArray(); 1051 int len = es.length; 1052 if (index < 0 || index > len) 1053 throw new IndexOutOfBoundsException(outOfBounds(index, len)); 1054 1055 return new COWIterator<E>(es, index); 1056 } 1057 1058 /** 1059 * Returns a {@link Spliterator} over the elements in this list. 1060 * 1061 * <p>The {@code Spliterator} reports {@link Spliterator#IMMUTABLE}, 1062 * {@link Spliterator#ORDERED}, {@link Spliterator#SIZED}, and 1063 * {@link Spliterator#SUBSIZED}. 1064 * 1065 * <p>The spliterator provides a snapshot of the state of the list 1066 * when the spliterator was constructed. No synchronization is needed while 1067 * operating on the spliterator. 1068 * 1069 * @return a {@code Spliterator} over the elements in this list 1070 * @since 1.8 1071 */ spliterator()1072 public Spliterator<E> spliterator() { 1073 return Spliterators.spliterator 1074 (getArray(), Spliterator.IMMUTABLE | Spliterator.ORDERED); 1075 } 1076 1077 static final class COWIterator<E> implements ListIterator<E> { 1078 /** Snapshot of the array */ 1079 private final Object[] snapshot; 1080 /** Index of element to be returned by subsequent call to next. */ 1081 private int cursor; 1082 COWIterator(Object[] es, int initialCursor)1083 COWIterator(Object[] es, int initialCursor) { 1084 cursor = initialCursor; 1085 snapshot = es; 1086 } 1087 hasNext()1088 public boolean hasNext() { 1089 return cursor < snapshot.length; 1090 } 1091 hasPrevious()1092 public boolean hasPrevious() { 1093 return cursor > 0; 1094 } 1095 1096 @SuppressWarnings("unchecked") next()1097 public E next() { 1098 if (! hasNext()) 1099 throw new NoSuchElementException(); 1100 return (E) snapshot[cursor++]; 1101 } 1102 1103 @SuppressWarnings("unchecked") previous()1104 public E previous() { 1105 if (! hasPrevious()) 1106 throw new NoSuchElementException(); 1107 return (E) snapshot[--cursor]; 1108 } 1109 nextIndex()1110 public int nextIndex() { 1111 return cursor; 1112 } 1113 previousIndex()1114 public int previousIndex() { 1115 return cursor - 1; 1116 } 1117 1118 /** 1119 * Not supported. Always throws UnsupportedOperationException. 1120 * @throws UnsupportedOperationException always; {@code remove} 1121 * is not supported by this iterator. 1122 */ remove()1123 public void remove() { 1124 throw new UnsupportedOperationException(); 1125 } 1126 1127 /** 1128 * Not supported. Always throws UnsupportedOperationException. 1129 * @throws UnsupportedOperationException always; {@code set} 1130 * is not supported by this iterator. 1131 */ set(E e)1132 public void set(E e) { 1133 throw new UnsupportedOperationException(); 1134 } 1135 1136 /** 1137 * Not supported. Always throws UnsupportedOperationException. 1138 * @throws UnsupportedOperationException always; {@code add} 1139 * is not supported by this iterator. 1140 */ add(E e)1141 public void add(E e) { 1142 throw new UnsupportedOperationException(); 1143 } 1144 1145 @Override forEachRemaining(Consumer<? super E> action)1146 public void forEachRemaining(Consumer<? super E> action) { 1147 Objects.requireNonNull(action); 1148 final int size = snapshot.length; 1149 int i = cursor; 1150 cursor = size; 1151 for (; i < size; i++) 1152 action.accept(elementAt(snapshot, i)); 1153 } 1154 } 1155 1156 /** 1157 * Returns a view of the portion of this list between 1158 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. 1159 * The returned list is backed by this list, so changes in the 1160 * returned list are reflected in this list. 1161 * 1162 * <p>The semantics of the list returned by this method become 1163 * undefined if the backing list (i.e., this list) is modified in 1164 * any way other than via the returned list. 1165 * 1166 * @param fromIndex low endpoint (inclusive) of the subList 1167 * @param toIndex high endpoint (exclusive) of the subList 1168 * @return a view of the specified range within this list 1169 * @throws IndexOutOfBoundsException {@inheritDoc} 1170 */ subList(int fromIndex, int toIndex)1171 public List<E> subList(int fromIndex, int toIndex) { 1172 synchronized (lock) { 1173 Object[] es = getArray(); 1174 int len = es.length; 1175 int size = toIndex - fromIndex; 1176 if (fromIndex < 0 || toIndex > len || size < 0) 1177 throw new IndexOutOfBoundsException(); 1178 return new COWSubList(es, fromIndex, size); 1179 } 1180 } 1181 1182 /** 1183 * Sublist for CopyOnWriteArrayList. 1184 */ 1185 private class COWSubList implements List<E>, RandomAccess { 1186 private final int offset; 1187 private int size; 1188 private Object[] expectedArray; 1189 COWSubList(Object[] es, int offset, int size)1190 COWSubList(Object[] es, int offset, int size) { 1191 // assert Thread.holdsLock(lock); 1192 expectedArray = es; 1193 this.offset = offset; 1194 this.size = size; 1195 } 1196 checkForComodification()1197 private void checkForComodification() { 1198 // assert Thread.holdsLock(lock); 1199 if (getArray() != expectedArray) 1200 throw new ConcurrentModificationException(); 1201 } 1202 getArrayChecked()1203 private Object[] getArrayChecked() { 1204 // assert Thread.holdsLock(lock); 1205 Object[] a = getArray(); 1206 if (a != expectedArray) 1207 throw new ConcurrentModificationException(); 1208 return a; 1209 } 1210 rangeCheck(int index)1211 private void rangeCheck(int index) { 1212 // assert Thread.holdsLock(lock); 1213 if (index < 0 || index >= size) 1214 throw new IndexOutOfBoundsException(outOfBounds(index, size)); 1215 } 1216 rangeCheckForAdd(int index)1217 private void rangeCheckForAdd(int index) { 1218 // assert Thread.holdsLock(lock); 1219 if (index < 0 || index > size) 1220 throw new IndexOutOfBoundsException(outOfBounds(index, size)); 1221 } 1222 toArray()1223 public Object[] toArray() { 1224 final Object[] es; 1225 final int offset; 1226 final int size; 1227 synchronized (lock) { 1228 es = getArrayChecked(); 1229 offset = this.offset; 1230 size = this.size; 1231 } 1232 return Arrays.copyOfRange(es, offset, offset + size); 1233 } 1234 1235 @SuppressWarnings("unchecked") toArray(T[] a)1236 public <T> T[] toArray(T[] a) { 1237 final Object[] es; 1238 final int offset; 1239 final int size; 1240 synchronized (lock) { 1241 es = getArrayChecked(); 1242 offset = this.offset; 1243 size = this.size; 1244 } 1245 if (a.length < size) 1246 return (T[]) Arrays.copyOfRange( 1247 es, offset, offset + size, a.getClass()); 1248 else { 1249 System.arraycopy(es, offset, a, 0, size); 1250 if (a.length > size) 1251 a[size] = null; 1252 return a; 1253 } 1254 } 1255 indexOf(Object o)1256 public int indexOf(Object o) { 1257 final Object[] es; 1258 final int offset; 1259 final int size; 1260 synchronized (lock) { 1261 es = getArrayChecked(); 1262 offset = this.offset; 1263 size = this.size; 1264 } 1265 int i = indexOfRange(o, es, offset, offset + size); 1266 return (i == -1) ? -1 : i - offset; 1267 } 1268 lastIndexOf(Object o)1269 public int lastIndexOf(Object o) { 1270 final Object[] es; 1271 final int offset; 1272 final int size; 1273 synchronized (lock) { 1274 es = getArrayChecked(); 1275 offset = this.offset; 1276 size = this.size; 1277 } 1278 int i = lastIndexOfRange(o, es, offset, offset + size); 1279 return (i == -1) ? -1 : i - offset; 1280 } 1281 contains(Object o)1282 public boolean contains(Object o) { 1283 return indexOf(o) >= 0; 1284 } 1285 containsAll(Collection<?> c)1286 public boolean containsAll(Collection<?> c) { 1287 final Object[] es; 1288 final int offset; 1289 final int size; 1290 synchronized (lock) { 1291 es = getArrayChecked(); 1292 offset = this.offset; 1293 size = this.size; 1294 } 1295 for (Object o : c) 1296 if (indexOfRange(o, es, offset, offset + size) < 0) 1297 return false; 1298 return true; 1299 } 1300 isEmpty()1301 public boolean isEmpty() { 1302 return size() == 0; 1303 } 1304 toString()1305 public String toString() { 1306 return Arrays.toString(toArray()); 1307 } 1308 hashCode()1309 public int hashCode() { 1310 final Object[] es; 1311 final int offset; 1312 final int size; 1313 synchronized (lock) { 1314 es = getArrayChecked(); 1315 offset = this.offset; 1316 size = this.size; 1317 } 1318 return hashCodeOfRange(es, offset, offset + size); 1319 } 1320 equals(Object o)1321 public boolean equals(Object o) { 1322 if (o == this) 1323 return true; 1324 if (!(o instanceof List)) 1325 return false; 1326 Iterator<?> it = ((List<?>)o).iterator(); 1327 1328 final Object[] es; 1329 final int offset; 1330 final int size; 1331 synchronized (lock) { 1332 es = getArrayChecked(); 1333 offset = this.offset; 1334 size = this.size; 1335 } 1336 1337 for (int i = offset, end = offset + size; i < end; i++) 1338 if (!it.hasNext() || !Objects.equals(es[i], it.next())) 1339 return false; 1340 return !it.hasNext(); 1341 } 1342 set(int index, E element)1343 public E set(int index, E element) { 1344 synchronized (lock) { 1345 rangeCheck(index); 1346 checkForComodification(); 1347 E x = CopyOnWriteArrayList.this.set(offset + index, element); 1348 expectedArray = getArray(); 1349 return x; 1350 } 1351 } 1352 get(int index)1353 public E get(int index) { 1354 synchronized (lock) { 1355 rangeCheck(index); 1356 checkForComodification(); 1357 return CopyOnWriteArrayList.this.get(offset + index); 1358 } 1359 } 1360 size()1361 public int size() { 1362 synchronized (lock) { 1363 checkForComodification(); 1364 return size; 1365 } 1366 } 1367 add(E element)1368 public boolean add(E element) { 1369 synchronized (lock) { 1370 checkForComodification(); 1371 CopyOnWriteArrayList.this.add(offset + size, element); 1372 expectedArray = getArray(); 1373 size++; 1374 } 1375 return true; 1376 } 1377 add(int index, E element)1378 public void add(int index, E element) { 1379 synchronized (lock) { 1380 checkForComodification(); 1381 rangeCheckForAdd(index); 1382 CopyOnWriteArrayList.this.add(offset + index, element); 1383 expectedArray = getArray(); 1384 size++; 1385 } 1386 } 1387 addAll(Collection<? extends E> c)1388 public boolean addAll(Collection<? extends E> c) { 1389 synchronized (lock) { 1390 final Object[] oldArray = getArrayChecked(); 1391 boolean modified = 1392 CopyOnWriteArrayList.this.addAll(offset + size, c); 1393 size += (expectedArray = getArray()).length - oldArray.length; 1394 return modified; 1395 } 1396 } 1397 addAll(int index, Collection<? extends E> c)1398 public boolean addAll(int index, Collection<? extends E> c) { 1399 synchronized (lock) { 1400 rangeCheckForAdd(index); 1401 final Object[] oldArray = getArrayChecked(); 1402 boolean modified = 1403 CopyOnWriteArrayList.this.addAll(offset + index, c); 1404 size += (expectedArray = getArray()).length - oldArray.length; 1405 return modified; 1406 } 1407 } 1408 clear()1409 public void clear() { 1410 synchronized (lock) { 1411 checkForComodification(); 1412 removeRange(offset, offset + size); 1413 expectedArray = getArray(); 1414 size = 0; 1415 } 1416 } 1417 remove(int index)1418 public E remove(int index) { 1419 synchronized (lock) { 1420 rangeCheck(index); 1421 checkForComodification(); 1422 E result = CopyOnWriteArrayList.this.remove(offset + index); 1423 expectedArray = getArray(); 1424 size--; 1425 return result; 1426 } 1427 } 1428 remove(Object o)1429 public boolean remove(Object o) { 1430 synchronized (lock) { 1431 checkForComodification(); 1432 int index = indexOf(o); 1433 if (index == -1) 1434 return false; 1435 remove(index); 1436 return true; 1437 } 1438 } 1439 iterator()1440 public Iterator<E> iterator() { 1441 return listIterator(0); 1442 } 1443 listIterator()1444 public ListIterator<E> listIterator() { 1445 return listIterator(0); 1446 } 1447 listIterator(int index)1448 public ListIterator<E> listIterator(int index) { 1449 synchronized (lock) { 1450 checkForComodification(); 1451 rangeCheckForAdd(index); 1452 return new COWSubListIterator<E>( 1453 CopyOnWriteArrayList.this, index, offset, size); 1454 } 1455 } 1456 subList(int fromIndex, int toIndex)1457 public List<E> subList(int fromIndex, int toIndex) { 1458 synchronized (lock) { 1459 checkForComodification(); 1460 if (fromIndex < 0 || toIndex > size || fromIndex > toIndex) 1461 throw new IndexOutOfBoundsException(); 1462 return new COWSubList(expectedArray, fromIndex + offset, toIndex - fromIndex); 1463 } 1464 } 1465 forEach(Consumer<? super E> action)1466 public void forEach(Consumer<? super E> action) { 1467 Objects.requireNonNull(action); 1468 int i, end; final Object[] es; 1469 synchronized (lock) { 1470 es = getArrayChecked(); 1471 i = offset; 1472 end = i + size; 1473 } 1474 for (; i < end; i++) 1475 action.accept(elementAt(es, i)); 1476 } 1477 replaceAll(UnaryOperator<E> operator)1478 public void replaceAll(UnaryOperator<E> operator) { 1479 synchronized (lock) { 1480 checkForComodification(); 1481 replaceAllRange(operator, offset, offset + size); 1482 expectedArray = getArray(); 1483 } 1484 } 1485 sort(Comparator<? super E> c)1486 public void sort(Comparator<? super E> c) { 1487 synchronized (lock) { 1488 checkForComodification(); 1489 sortRange(c, offset, offset + size); 1490 expectedArray = getArray(); 1491 } 1492 } 1493 removeAll(Collection<?> c)1494 public boolean removeAll(Collection<?> c) { 1495 Objects.requireNonNull(c); 1496 return bulkRemove(e -> c.contains(e)); 1497 } 1498 retainAll(Collection<?> c)1499 public boolean retainAll(Collection<?> c) { 1500 Objects.requireNonNull(c); 1501 return bulkRemove(e -> !c.contains(e)); 1502 } 1503 removeIf(Predicate<? super E> filter)1504 public boolean removeIf(Predicate<? super E> filter) { 1505 Objects.requireNonNull(filter); 1506 return bulkRemove(filter); 1507 } 1508 bulkRemove(Predicate<? super E> filter)1509 private boolean bulkRemove(Predicate<? super E> filter) { 1510 synchronized (lock) { 1511 final Object[] oldArray = getArrayChecked(); 1512 boolean modified = CopyOnWriteArrayList.this.bulkRemove( 1513 filter, offset, offset + size); 1514 size += (expectedArray = getArray()).length - oldArray.length; 1515 return modified; 1516 } 1517 } 1518 spliterator()1519 public Spliterator<E> spliterator() { 1520 synchronized (lock) { 1521 return Spliterators.spliterator( 1522 getArrayChecked(), offset, offset + size, 1523 Spliterator.IMMUTABLE | Spliterator.ORDERED); 1524 } 1525 } 1526 1527 } 1528 1529 private static class COWSubListIterator<E> implements ListIterator<E> { 1530 private final ListIterator<E> it; 1531 private final int offset; 1532 private final int size; 1533 COWSubListIterator(List<E> l, int index, int offset, int size)1534 COWSubListIterator(List<E> l, int index, int offset, int size) { 1535 this.offset = offset; 1536 this.size = size; 1537 it = l.listIterator(index + offset); 1538 } 1539 hasNext()1540 public boolean hasNext() { 1541 return nextIndex() < size; 1542 } 1543 next()1544 public E next() { 1545 if (hasNext()) 1546 return it.next(); 1547 else 1548 throw new NoSuchElementException(); 1549 } 1550 hasPrevious()1551 public boolean hasPrevious() { 1552 return previousIndex() >= 0; 1553 } 1554 previous()1555 public E previous() { 1556 if (hasPrevious()) 1557 return it.previous(); 1558 else 1559 throw new NoSuchElementException(); 1560 } 1561 nextIndex()1562 public int nextIndex() { 1563 return it.nextIndex() - offset; 1564 } 1565 previousIndex()1566 public int previousIndex() { 1567 return it.previousIndex() - offset; 1568 } 1569 remove()1570 public void remove() { 1571 throw new UnsupportedOperationException(); 1572 } 1573 set(E e)1574 public void set(E e) { 1575 throw new UnsupportedOperationException(); 1576 } 1577 add(E e)1578 public void add(E e) { 1579 throw new UnsupportedOperationException(); 1580 } 1581 1582 @Override 1583 @SuppressWarnings("unchecked") forEachRemaining(Consumer<? super E> action)1584 public void forEachRemaining(Consumer<? super E> action) { 1585 Objects.requireNonNull(action); 1586 while (hasNext()) { 1587 action.accept(it.next()); 1588 } 1589 } 1590 } 1591 1592 /** Initializes the lock; for use when deserializing or cloning. */ resetLock()1593 private void resetLock() { 1594 Field lockField = java.security.AccessController.doPrivileged( 1595 (java.security.PrivilegedAction<Field>) () -> { 1596 try { 1597 Field f = CopyOnWriteArrayList.class 1598 .getDeclaredField("lock"); 1599 f.setAccessible(true); 1600 return f; 1601 } catch (ReflectiveOperationException e) { 1602 throw new Error(e); 1603 }}); 1604 try { 1605 lockField.set(this, new Object()); 1606 } catch (IllegalAccessException e) { 1607 throw new Error(e); 1608 } 1609 } 1610 } 1611