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.Collections; 43 import java.util.Comparator; 44 import java.util.ConcurrentModificationException; 45 import java.util.Iterator; 46 import java.util.List; 47 import java.util.ListIterator; 48 import java.util.NoSuchElementException; 49 import java.util.Objects; 50 import java.util.RandomAccess; 51 import java.util.Spliterator; 52 import java.util.Spliterators; 53 import java.util.function.Consumer; 54 import java.util.function.IntFunction; 55 import java.util.function.Predicate; 56 import java.util.function.UnaryOperator; 57 import java.util.stream.Stream; 58 import java.util.stream.StreamSupport; 59 import jdk.internal.access.SharedSecrets; 60 import jdk.internal.util.ArraysSupport; 61 62 // Android-changed: Removed javadoc link to collections framework docs 63 /** 64 * A thread-safe variant of {@link java.util.ArrayList} in which all mutative 65 * operations ({@code add}, {@code set}, and so on) are implemented by 66 * making a fresh copy of the underlying array. 67 * 68 * <p>This is ordinarily too costly, but may be <em>more</em> efficient 69 * than alternatives when traversal operations vastly outnumber 70 * mutations, and is useful when you cannot or don't want to 71 * synchronize traversals, yet need to preclude interference among 72 * concurrent threads. The "snapshot" style iterator method uses a 73 * reference to the state of the array at the point that the iterator 74 * was created. This array never changes during the lifetime of the 75 * iterator, so interference is impossible and the iterator is 76 * guaranteed not to throw {@code ConcurrentModificationException}. 77 * The iterator will not reflect additions, removals, or changes to 78 * the list since the iterator was created. Element-changing 79 * operations on iterators themselves ({@code remove}, {@code set}, and 80 * {@code add}) are not supported. These methods throw 81 * {@code UnsupportedOperationException}. 82 * 83 * <p>All elements are permitted, including {@code null}. 84 * 85 * <p>Memory consistency effects: As with other concurrent 86 * collections, actions in a thread prior to placing an object into a 87 * {@code CopyOnWriteArrayList} 88 * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a> 89 * actions subsequent to the access or removal of that element from 90 * the {@code CopyOnWriteArrayList} in another thread. 91 * 92 * <p>This class is a member of the 93 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework"> 94 * Java Collections Framework</a>. 95 * 96 * @since 1.5 97 * @author Doug Lea 98 * @param <E> the type of elements held in this list 99 */ 100 public class CopyOnWriteArrayList<E> 101 implements List<E>, RandomAccess, Cloneable, java.io.Serializable { 102 private static final long serialVersionUID = 8673264195747942595L; 103 104 /** 105 * The lock protecting all mutators. (We have a mild preference 106 * for builtin monitors over ReentrantLock when either will do.) 107 */ 108 final transient Object lock = new Object(); 109 110 /** The array, accessed only via getArray/setArray. */ 111 private transient volatile Object[] array; 112 113 /** 114 * Gets the array. Non-private so as to also be accessible 115 * from CopyOnWriteArraySet class. 116 */ getArray()117 final Object[] getArray() { 118 return array; 119 } 120 121 /** 122 * Sets the array. 123 */ setArray(Object[] a)124 final void setArray(Object[] a) { 125 array = a; 126 } 127 128 /** 129 * Creates an empty list. 130 */ CopyOnWriteArrayList()131 public CopyOnWriteArrayList() { 132 setArray(new Object[0]); 133 } 134 135 /** 136 * Creates a list containing the elements of the specified 137 * collection, in the order they are returned by the collection's 138 * iterator. 139 * 140 * @param c the collection of initially held elements 141 * @throws NullPointerException if the specified collection is null 142 */ CopyOnWriteArrayList(Collection<? extends E> c)143 public CopyOnWriteArrayList(Collection<? extends E> c) { 144 Object[] es; 145 if (c.getClass() == CopyOnWriteArrayList.class) 146 es = ((CopyOnWriteArrayList<?>)c).getArray(); 147 else { 148 es = c.toArray(); 149 // Android-changed: Defend against c.toArray (incorrectly) not returning Object[] 150 // (see b/204397945) 151 // if (c.getClass() != java.util.ArrayList.class) 152 if (es.getClass() != Object[].class) 153 es = Arrays.copyOf(es, es.length, Object[].class); 154 } 155 setArray(es); 156 } 157 158 /** 159 * Creates a list holding a copy of the given array. 160 * 161 * @param toCopyIn the array (a copy of this array is used as the 162 * internal array) 163 * @throws NullPointerException if the specified array is null 164 */ CopyOnWriteArrayList(E[] toCopyIn)165 public CopyOnWriteArrayList(E[] toCopyIn) { 166 setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class)); 167 } 168 169 /** 170 * Returns the number of elements in this list. 171 * 172 * @return the number of elements in this list 173 */ size()174 public int size() { 175 return getArray().length; 176 } 177 178 /** 179 * Returns {@code true} if this list contains no elements. 180 * 181 * @return {@code true} if this list contains no elements 182 */ isEmpty()183 public boolean isEmpty() { 184 return size() == 0; 185 } 186 187 /** 188 * static version of indexOf, to allow repeated calls without 189 * needing to re-acquire array each time. 190 * @param o element to search for 191 * @param es the array 192 * @param from first index to search 193 * @param to one past last index to search 194 * @return index of element, or -1 if absent 195 */ indexOfRange(Object o, Object[] es, int from, int to)196 private static int indexOfRange(Object o, Object[] es, int from, int to) { 197 if (o == null) { 198 for (int i = from; i < to; i++) 199 if (es[i] == null) 200 return i; 201 } else { 202 for (int i = from; i < to; i++) 203 if (o.equals(es[i])) 204 return i; 205 } 206 return -1; 207 } 208 209 /** 210 * static version of lastIndexOf. 211 * @param o element to search for 212 * @param es the array 213 * @param from index of first element of range, last element to search 214 * @param to one past last element of range, first element to search 215 * @return index of element, or -1 if absent 216 */ lastIndexOfRange(Object o, Object[] es, int from, int to)217 private static int lastIndexOfRange(Object o, Object[] es, int from, int to) { 218 if (o == null) { 219 for (int i = to - 1; i >= from; i--) 220 if (es[i] == null) 221 return i; 222 } else { 223 for (int i = to - 1; i >= from; i--) 224 if (o.equals(es[i])) 225 return i; 226 } 227 return -1; 228 } 229 230 /** 231 * Returns {@code true} if this list contains the specified element. 232 * More formally, returns {@code true} if and only if this list contains 233 * at least one element {@code e} such that {@code Objects.equals(o, e)}. 234 * 235 * @param o element whose presence in this list is to be tested 236 * @return {@code true} if this list contains the specified element 237 */ contains(Object o)238 public boolean contains(Object o) { 239 return indexOf(o) >= 0; 240 } 241 242 /** 243 * {@inheritDoc} 244 */ indexOf(Object o)245 public int indexOf(Object o) { 246 Object[] es = getArray(); 247 return indexOfRange(o, es, 0, es.length); 248 } 249 250 /** 251 * Returns the index of the first occurrence of the specified element in 252 * this list, searching forwards from {@code index}, or returns -1 if 253 * the element is not found. 254 * More formally, returns the lowest index {@code i} such that 255 * {@code i >= index && Objects.equals(get(i), e)}, 256 * or -1 if there is no such index. 257 * 258 * @param e element to search for 259 * @param index index to start searching from 260 * @return the index of the first occurrence of the element in 261 * this list at position {@code index} or later in the list; 262 * {@code -1} if the element is not found. 263 * @throws IndexOutOfBoundsException if the specified index is negative 264 */ indexOf(E e, int index)265 public int indexOf(E e, int index) { 266 Object[] es = getArray(); 267 return indexOfRange(e, es, index, es.length); 268 } 269 270 /** 271 * {@inheritDoc} 272 */ lastIndexOf(Object o)273 public int lastIndexOf(Object o) { 274 Object[] es = getArray(); 275 return lastIndexOfRange(o, es, 0, es.length); 276 } 277 278 /** 279 * Returns the index of the last occurrence of the specified element in 280 * this list, searching backwards from {@code index}, or returns -1 if 281 * the element is not found. 282 * More formally, returns the highest index {@code i} such that 283 * {@code i <= index && Objects.equals(get(i), e)}, 284 * or -1 if there is no such index. 285 * 286 * @param e element to search for 287 * @param index index to start searching backwards from 288 * @return the index of the last occurrence of the element at position 289 * less than or equal to {@code index} in this list; 290 * -1 if the element is not found. 291 * @throws IndexOutOfBoundsException if the specified index is greater 292 * than or equal to the current size of this list 293 */ lastIndexOf(E e, int index)294 public int lastIndexOf(E e, int index) { 295 Object[] es = getArray(); 296 return lastIndexOfRange(e, es, 0, index + 1); 297 } 298 299 /** 300 * Returns a shallow copy of this list. (The elements themselves 301 * are not copied.) 302 * 303 * @return a clone of this list 304 */ clone()305 public Object clone() { 306 try { 307 @SuppressWarnings("unchecked") 308 CopyOnWriteArrayList<E> clone = 309 (CopyOnWriteArrayList<E>) super.clone(); 310 clone.resetLock(); 311 // Unlike in readObject, here we cannot visibility-piggyback on the 312 // volatile write in setArray(). 313 VarHandle.releaseFence(); 314 return clone; 315 } catch (CloneNotSupportedException e) { 316 // this shouldn't happen, since we are Cloneable 317 throw new InternalError(); 318 } 319 } 320 321 /** 322 * Returns an array containing all of the elements in this list 323 * in proper sequence (from first to last element). 324 * 325 * <p>The returned array will be "safe" in that no references to it are 326 * maintained by this list. (In other words, this method must allocate 327 * a new array). The caller is thus free to modify the returned array. 328 * 329 * <p>This method acts as bridge between array-based and collection-based 330 * APIs. 331 * 332 * @return an array containing all the elements in this list 333 */ toArray()334 public Object[] toArray() { 335 return getArray().clone(); 336 } 337 338 /** 339 * Returns an array containing all of the elements in this list in 340 * proper sequence (from first to last element); the runtime type of 341 * the returned array is that of the specified array. If the list fits 342 * in the specified array, it is returned therein. Otherwise, a new 343 * array is allocated with the runtime type of the specified array and 344 * the size of this list. 345 * 346 * <p>If this list fits in the specified array with room to spare 347 * (i.e., the array has more elements than this list), the element in 348 * the array immediately following the end of the list is set to 349 * {@code null}. (This is useful in determining the length of this 350 * list <i>only</i> if the caller knows that this list does not contain 351 * any null elements.) 352 * 353 * <p>Like the {@link #toArray()} method, this method acts as bridge between 354 * array-based and collection-based APIs. Further, this method allows 355 * precise control over the runtime type of the output array, and may, 356 * under certain circumstances, be used to save allocation costs. 357 * 358 * <p>Suppose {@code x} is a list known to contain only strings. 359 * The following code can be used to dump the list into a newly 360 * allocated array of {@code String}: 361 * 362 * <pre> {@code String[] y = x.toArray(new String[0]);}</pre> 363 * 364 * Note that {@code toArray(new Object[0])} is identical in function to 365 * {@code toArray()}. 366 * 367 * @param a the array into which the elements of the list are to 368 * be stored, if it is big enough; otherwise, a new array of the 369 * same runtime type is allocated for this purpose. 370 * @return an array containing all the elements in this list 371 * @throws ArrayStoreException if the runtime type of the specified array 372 * is not a supertype of the runtime type of every element in 373 * this list 374 * @throws NullPointerException if the specified array is null 375 */ 376 @SuppressWarnings("unchecked") toArray(T[] a)377 public <T> T[] toArray(T[] a) { 378 Object[] es = getArray(); 379 int len = es.length; 380 if (a.length < len) 381 return (T[]) Arrays.copyOf(es, len, a.getClass()); 382 else { 383 System.arraycopy(es, 0, a, 0, len); 384 if (a.length > len) 385 a[len] = null; 386 return a; 387 } 388 } 389 390 // Positional Access Operations 391 392 @SuppressWarnings("unchecked") elementAt(Object[] a, int index)393 static <E> E elementAt(Object[] a, int index) { 394 return (E) a[index]; 395 } 396 outOfBounds(int index, int size)397 static String outOfBounds(int index, int size) { 398 return "Index: " + index + ", Size: " + size; 399 } 400 401 /** 402 * {@inheritDoc} 403 * 404 * @throws IndexOutOfBoundsException {@inheritDoc} 405 */ get(int index)406 public E get(int index) { 407 return elementAt(getArray(), index); 408 } 409 410 /** 411 * {@inheritDoc} 412 * 413 * @throws NoSuchElementException {@inheritDoc} 414 * @since 21 415 */ getFirst()416 public E getFirst() { 417 Object[] es = getArray(); 418 if (es.length == 0) 419 throw new NoSuchElementException(); 420 else 421 return elementAt(es, 0); 422 } 423 424 /** 425 * {@inheritDoc} 426 * 427 * @throws NoSuchElementException {@inheritDoc} 428 * @since 21 429 */ getLast()430 public E getLast() { 431 Object[] es = getArray(); 432 if (es.length == 0) 433 throw new NoSuchElementException(); 434 else 435 return elementAt(es, es.length - 1); 436 } 437 438 /** 439 * Replaces the element at the specified position in this list with the 440 * specified element. 441 * 442 * @throws IndexOutOfBoundsException {@inheritDoc} 443 */ set(int index, E element)444 public E set(int index, E element) { 445 synchronized (lock) { 446 Object[] es = getArray(); 447 E oldValue = elementAt(es, index); 448 449 if (oldValue != element) { 450 es = es.clone(); 451 es[index] = element; 452 } 453 // Ensure volatile write semantics even when oldvalue == element 454 setArray(es); 455 return oldValue; 456 } 457 } 458 459 /** 460 * Appends the specified element to the end of this list. 461 * 462 * @param e element to be appended to this list 463 * @return {@code true} (as specified by {@link Collection#add}) 464 */ add(E e)465 public boolean add(E e) { 466 synchronized (lock) { 467 Object[] es = getArray(); 468 int len = es.length; 469 es = Arrays.copyOf(es, len + 1); 470 es[len] = e; 471 setArray(es); 472 return true; 473 } 474 } 475 476 /** 477 * Inserts the specified element at the specified position in this 478 * list. Shifts the element currently at that position (if any) and 479 * any subsequent elements to the right (adds one to their indices). 480 * 481 * @throws IndexOutOfBoundsException {@inheritDoc} 482 */ add(int index, E element)483 public void add(int index, E element) { 484 synchronized (lock) { 485 Object[] es = getArray(); 486 int len = es.length; 487 if (index > len || index < 0) 488 throw new IndexOutOfBoundsException(outOfBounds(index, len)); 489 Object[] newElements; 490 int numMoved = len - index; 491 if (numMoved == 0) 492 newElements = Arrays.copyOf(es, len + 1); 493 else { 494 newElements = new Object[len + 1]; 495 System.arraycopy(es, 0, newElements, 0, index); 496 System.arraycopy(es, index, newElements, index + 1, 497 numMoved); 498 } 499 newElements[index] = element; 500 setArray(newElements); 501 } 502 } 503 504 /** 505 * {@inheritDoc} 506 * 507 * @since 21 508 */ addFirst(E e)509 public void addFirst(E e) { 510 add(0, e); 511 } 512 513 /** 514 * {@inheritDoc} 515 * 516 * @since 21 517 */ addLast(E e)518 public void addLast(E e) { 519 synchronized (lock) { 520 add(getArray().length, e); 521 } 522 } 523 524 /** 525 * Removes the element at the specified position in this list. 526 * Shifts any subsequent elements to the left (subtracts one from their 527 * indices). Returns the element that was removed from the list. 528 * 529 * @throws IndexOutOfBoundsException {@inheritDoc} 530 */ remove(int index)531 public E remove(int index) { 532 synchronized (lock) { 533 Object[] es = getArray(); 534 int len = es.length; 535 E oldValue = elementAt(es, index); 536 int numMoved = len - index - 1; 537 Object[] newElements; 538 if (numMoved == 0) 539 newElements = Arrays.copyOf(es, len - 1); 540 else { 541 newElements = new Object[len - 1]; 542 System.arraycopy(es, 0, newElements, 0, index); 543 System.arraycopy(es, index + 1, newElements, index, 544 numMoved); 545 } 546 setArray(newElements); 547 return oldValue; 548 } 549 } 550 551 /** 552 * {@inheritDoc} 553 * 554 * @throws NoSuchElementException {@inheritDoc} 555 * @since 21 556 */ removeFirst()557 public E removeFirst() { 558 synchronized (lock) { 559 if (getArray().length == 0) 560 throw new NoSuchElementException(); 561 else 562 return remove(0); 563 } 564 } 565 566 /** 567 * {@inheritDoc} 568 * 569 * @throws NoSuchElementException {@inheritDoc} 570 * @since 21 571 */ removeLast()572 public E removeLast() { 573 synchronized (lock) { 574 int size = getArray().length; 575 if (size == 0) 576 throw new NoSuchElementException(); 577 else 578 return remove(size - 1); 579 } 580 } 581 582 /** 583 * Removes the first occurrence of the specified element from this list, 584 * if it is present. If this list does not contain the element, it is 585 * unchanged. More formally, removes the element with the lowest index 586 * {@code i} such that {@code Objects.equals(o, get(i))} 587 * (if such an element exists). Returns {@code true} if this list 588 * contained the specified element (or equivalently, if this list 589 * changed as a result of the call). 590 * 591 * @param o element to be removed from this list, if present 592 * @return {@code true} if this list contained the specified element 593 */ remove(Object o)594 public boolean remove(Object o) { 595 Object[] snapshot = getArray(); 596 int index = indexOfRange(o, snapshot, 0, snapshot.length); 597 return index >= 0 && remove(o, snapshot, index); 598 } 599 600 /** 601 * A version of remove(Object) using the strong hint that given 602 * recent snapshot contains o at the given index. 603 */ remove(Object o, Object[] snapshot, int index)604 private boolean remove(Object o, Object[] snapshot, int index) { 605 synchronized (lock) { 606 Object[] current = getArray(); 607 int len = current.length; 608 if (snapshot != current) findIndex: { 609 int prefix = Math.min(index, len); 610 for (int i = 0; i < prefix; i++) { 611 if (current[i] != snapshot[i] 612 && Objects.equals(o, current[i])) { 613 index = i; 614 break findIndex; 615 } 616 } 617 if (index >= len) 618 return false; 619 if (current[index] == o) 620 break findIndex; 621 index = indexOfRange(o, current, index, len); 622 if (index < 0) 623 return false; 624 } 625 Object[] newElements = new Object[len - 1]; 626 System.arraycopy(current, 0, newElements, 0, index); 627 System.arraycopy(current, index + 1, 628 newElements, index, 629 len - index - 1); 630 setArray(newElements); 631 return true; 632 } 633 } 634 635 /** 636 * Removes from this list all of the elements whose index is between 637 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. 638 * Shifts any succeeding elements to the left (reduces their index). 639 * This call shortens the list by {@code (toIndex - fromIndex)} elements. 640 * (If {@code toIndex==fromIndex}, this operation has no effect.) 641 * 642 * @param fromIndex index of first element to be removed 643 * @param toIndex index after last element to be removed 644 * @throws IndexOutOfBoundsException if fromIndex or toIndex out of range 645 * ({@code fromIndex < 0 || toIndex > size() || toIndex < fromIndex}) 646 */ removeRange(int fromIndex, int toIndex)647 void removeRange(int fromIndex, int toIndex) { 648 synchronized (lock) { 649 Object[] es = getArray(); 650 int len = es.length; 651 652 if (fromIndex < 0 || toIndex > len || toIndex < fromIndex) 653 throw new IndexOutOfBoundsException(); 654 int newlen = len - (toIndex - fromIndex); 655 int numMoved = len - toIndex; 656 if (numMoved == 0) 657 setArray(Arrays.copyOf(es, newlen)); 658 else { 659 Object[] newElements = new Object[newlen]; 660 System.arraycopy(es, 0, newElements, 0, fromIndex); 661 System.arraycopy(es, toIndex, newElements, 662 fromIndex, numMoved); 663 setArray(newElements); 664 } 665 } 666 } 667 668 /** 669 * Appends the element, if not present. 670 * 671 * @param e element to be added to this list, if absent 672 * @return {@code true} if the element was added 673 */ addIfAbsent(E e)674 public boolean addIfAbsent(E e) { 675 Object[] snapshot = getArray(); 676 return indexOfRange(e, snapshot, 0, snapshot.length) < 0 677 && addIfAbsent(e, snapshot); 678 } 679 680 /** 681 * A version of addIfAbsent using the strong hint that given 682 * recent snapshot does not contain e. 683 */ addIfAbsent(E e, Object[] snapshot)684 private boolean addIfAbsent(E e, Object[] snapshot) { 685 synchronized (lock) { 686 Object[] current = getArray(); 687 int len = current.length; 688 if (snapshot != current) { 689 // Optimize for lost race to another addXXX operation 690 int common = Math.min(snapshot.length, len); 691 for (int i = 0; i < common; i++) 692 if (current[i] != snapshot[i] 693 && Objects.equals(e, current[i])) 694 return false; 695 if (indexOfRange(e, current, common, len) >= 0) 696 return false; 697 } 698 Object[] newElements = Arrays.copyOf(current, len + 1); 699 newElements[len] = e; 700 setArray(newElements); 701 return true; 702 } 703 } 704 705 /** 706 * Returns {@code true} if this list contains all of the elements of the 707 * specified collection. 708 * 709 * @param c collection to be checked for containment in this list 710 * @return {@code true} if this list contains all of the elements of the 711 * specified collection 712 * @throws NullPointerException if the specified collection is null 713 * @see #contains(Object) 714 */ containsAll(Collection<?> c)715 public boolean containsAll(Collection<?> c) { 716 Object[] es = getArray(); 717 int len = es.length; 718 for (Object e : c) { 719 if (indexOfRange(e, es, 0, len) < 0) 720 return false; 721 } 722 return true; 723 } 724 725 /** 726 * Removes from this list all of its elements that are contained in 727 * the specified collection. This is a particularly expensive operation 728 * in this class because of the need for an internal temporary array. 729 * 730 * @param c collection containing elements to be removed from this list 731 * @return {@code true} if this list changed as a result of the call 732 * @throws ClassCastException if the class of an element of this list 733 * is incompatible with the specified collection 734 * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>) 735 * @throws NullPointerException if this list contains a null element and the 736 * specified collection does not permit null elements 737 * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>), 738 * or if the specified collection is null 739 * @see #remove(Object) 740 */ removeAll(Collection<?> c)741 public boolean removeAll(Collection<?> c) { 742 Objects.requireNonNull(c); 743 return bulkRemove(e -> c.contains(e)); 744 } 745 746 /** 747 * Retains only the elements in this list that are contained in the 748 * specified collection. In other words, removes from this list all of 749 * its elements that are not contained in the specified collection. 750 * 751 * @param c collection containing elements to be retained in this list 752 * @return {@code true} if this list changed as a result of the call 753 * @throws ClassCastException if the class of an element of this list 754 * is incompatible with the specified collection 755 * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>) 756 * @throws NullPointerException if this list contains a null element and the 757 * specified collection does not permit null elements 758 * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>), 759 * or if the specified collection is null 760 * @see #remove(Object) 761 */ retainAll(Collection<?> c)762 public boolean retainAll(Collection<?> c) { 763 Objects.requireNonNull(c); 764 return bulkRemove(e -> !c.contains(e)); 765 } 766 767 /** 768 * Appends all of the elements in the specified collection that 769 * are not already contained in this list, to the end of 770 * this list, in the order that they are returned by the 771 * specified collection's iterator. 772 * 773 * @param c collection containing elements to be added to this list 774 * @return the number of elements added 775 * @throws NullPointerException if the specified collection is null 776 * @see #addIfAbsent(Object) 777 */ addAllAbsent(Collection<? extends E> c)778 public int addAllAbsent(Collection<? extends E> c) { 779 Object[] cs = c.toArray(); 780 if (c.getClass() != ArrayList.class) { 781 cs = cs.clone(); 782 } 783 if (cs.length == 0) 784 return 0; 785 synchronized (lock) { 786 Object[] es = getArray(); 787 int len = es.length; 788 int added = 0; 789 // uniquify and compact elements in cs 790 for (int i = 0; i < cs.length; ++i) { 791 Object e = cs[i]; 792 if (indexOfRange(e, es, 0, len) < 0 && 793 indexOfRange(e, cs, 0, added) < 0) 794 cs[added++] = e; 795 } 796 if (added > 0) { 797 Object[] newElements = Arrays.copyOf(es, len + added); 798 System.arraycopy(cs, 0, newElements, len, added); 799 setArray(newElements); 800 } 801 return added; 802 } 803 } 804 805 /** 806 * Removes all of the elements from this list. 807 * The list will be empty after this call returns. 808 */ clear()809 public void clear() { 810 synchronized (lock) { 811 setArray(new Object[0]); 812 } 813 } 814 815 /** 816 * Appends all of the elements in the specified collection to the end 817 * of this list, in the order that they are returned by the specified 818 * collection's iterator. 819 * 820 * @param c collection containing elements to be added to this list 821 * @return {@code true} if this list changed as a result of the call 822 * @throws NullPointerException if the specified collection is null 823 * @see #add(Object) 824 */ addAll(Collection<? extends E> c)825 public boolean addAll(Collection<? extends E> c) { 826 Object[] cs = (c.getClass() == CopyOnWriteArrayList.class) ? 827 ((CopyOnWriteArrayList<?>)c).getArray() : c.toArray(); 828 if (cs.length == 0) 829 return false; 830 synchronized (lock) { 831 Object[] es = getArray(); 832 int len = es.length; 833 Object[] newElements; 834 if (len == 0 && (c.getClass() == CopyOnWriteArrayList.class || 835 c.getClass() == ArrayList.class)) { 836 newElements = cs; 837 } else { 838 newElements = Arrays.copyOf(es, len + cs.length); 839 System.arraycopy(cs, 0, newElements, len, cs.length); 840 } 841 setArray(newElements); 842 return true; 843 } 844 } 845 846 /** 847 * Inserts all of the elements in the specified collection into this 848 * list, starting at the specified position. Shifts the element 849 * currently at that position (if any) and any subsequent elements to 850 * the right (increases their indices). The new elements will appear 851 * in this list in the order that they are returned by the 852 * specified collection's iterator. 853 * 854 * @param index index at which to insert the first element 855 * from the specified collection 856 * @param c collection containing elements to be added to this list 857 * @return {@code true} if this list changed as a result of the call 858 * @throws IndexOutOfBoundsException {@inheritDoc} 859 * @throws NullPointerException if the specified collection is null 860 * @see #add(int,Object) 861 */ addAll(int index, Collection<? extends E> c)862 public boolean addAll(int index, Collection<? extends E> c) { 863 Object[] cs = c.toArray(); 864 synchronized (lock) { 865 Object[] es = getArray(); 866 int len = es.length; 867 if (index > len || index < 0) 868 throw new IndexOutOfBoundsException(outOfBounds(index, len)); 869 if (cs.length == 0) 870 return false; 871 int numMoved = len - index; 872 Object[] newElements; 873 if (numMoved == 0) 874 newElements = Arrays.copyOf(es, len + cs.length); 875 else { 876 newElements = new Object[len + cs.length]; 877 System.arraycopy(es, 0, newElements, 0, index); 878 System.arraycopy(es, index, 879 newElements, index + cs.length, 880 numMoved); 881 } 882 System.arraycopy(cs, 0, newElements, index, cs.length); 883 setArray(newElements); 884 return true; 885 } 886 } 887 888 /** 889 * @throws NullPointerException {@inheritDoc} 890 */ forEach(Consumer<? super E> action)891 public void forEach(Consumer<? super E> action) { 892 Objects.requireNonNull(action); 893 for (Object x : getArray()) { 894 @SuppressWarnings("unchecked") E e = (E) x; 895 action.accept(e); 896 } 897 } 898 899 /** 900 * @throws NullPointerException {@inheritDoc} 901 */ removeIf(Predicate<? super E> filter)902 public boolean removeIf(Predicate<? super E> filter) { 903 Objects.requireNonNull(filter); 904 return bulkRemove(filter); 905 } 906 907 // A tiny bit set implementation 908 nBits(int n)909 private static long[] nBits(int n) { 910 return new long[((n - 1) >> 6) + 1]; 911 } setBit(long[] bits, int i)912 private static void setBit(long[] bits, int i) { 913 bits[i >> 6] |= 1L << i; 914 } isClear(long[] bits, int i)915 private static boolean isClear(long[] bits, int i) { 916 return (bits[i >> 6] & (1L << i)) == 0; 917 } 918 bulkRemove(Predicate<? super E> filter)919 private boolean bulkRemove(Predicate<? super E> filter) { 920 synchronized (lock) { 921 return bulkRemove(filter, 0, getArray().length); 922 } 923 } 924 bulkRemove(Predicate<? super E> filter, int i, int end)925 boolean bulkRemove(Predicate<? super E> filter, int i, int end) { 926 // assert Thread.holdsLock(lock); 927 final Object[] es = getArray(); 928 // Optimize for initial run of survivors 929 for (; i < end && !filter.test(elementAt(es, i)); i++) 930 ; 931 if (i < end) { 932 final int beg = i; 933 final long[] deathRow = nBits(end - beg); 934 int deleted = 1; 935 deathRow[0] = 1L; // set bit 0 936 for (i = beg + 1; i < end; i++) 937 if (filter.test(elementAt(es, i))) { 938 setBit(deathRow, i - beg); 939 deleted++; 940 } 941 // Did filter reentrantly modify the list? 942 if (es != getArray()) 943 throw new ConcurrentModificationException(); 944 final Object[] newElts = Arrays.copyOf(es, es.length - deleted); 945 int w = beg; 946 for (i = beg; i < end; i++) 947 if (isClear(deathRow, i - beg)) 948 newElts[w++] = es[i]; 949 System.arraycopy(es, i, newElts, w, es.length - i); 950 setArray(newElts); 951 return true; 952 } else { 953 if (es != getArray()) 954 throw new ConcurrentModificationException(); 955 return false; 956 } 957 } 958 replaceAll(UnaryOperator<E> operator)959 public void replaceAll(UnaryOperator<E> operator) { 960 synchronized (lock) { 961 replaceAllRange(operator, 0, getArray().length); 962 } 963 } 964 replaceAllRange(UnaryOperator<E> operator, int i, int end)965 void replaceAllRange(UnaryOperator<E> operator, int i, int end) { 966 // assert Thread.holdsLock(lock); 967 Objects.requireNonNull(operator); 968 final Object[] es = getArray().clone(); 969 for (; i < end; i++) 970 es[i] = operator.apply(elementAt(es, i)); 971 setArray(es); 972 } 973 sort(Comparator<? super E> c)974 public void sort(Comparator<? super E> c) { 975 synchronized (lock) { 976 sortRange(c, 0, getArray().length); 977 } 978 } 979 980 @SuppressWarnings("unchecked") sortRange(Comparator<? super E> c, int i, int end)981 void sortRange(Comparator<? super E> c, int i, int end) { 982 // assert Thread.holdsLock(lock); 983 final Object[] es = getArray().clone(); 984 Arrays.sort(es, i, end, (Comparator<Object>)c); 985 setArray(es); 986 } 987 988 /** 989 * Saves this list to a stream (that is, serializes it). 990 * 991 * @param s the stream 992 * @throws java.io.IOException if an I/O error occurs 993 * @serialData The length of the array backing the list is emitted 994 * (int), followed by all of its elements (each an Object) 995 * in the proper order. 996 */ writeObject(java.io.ObjectOutputStream s)997 private void writeObject(java.io.ObjectOutputStream s) 998 throws java.io.IOException { 999 1000 s.defaultWriteObject(); 1001 1002 Object[] es = getArray(); 1003 // Write out array length 1004 s.writeInt(es.length); 1005 1006 // Write out all elements in the proper order. 1007 for (Object element : es) 1008 s.writeObject(element); 1009 } 1010 1011 /** 1012 * Reconstitutes this list from a stream (that is, deserializes it). 1013 * @param s the stream 1014 * @throws ClassNotFoundException if the class of a serialized object 1015 * could not be found 1016 * @throws java.io.IOException if an I/O error occurs 1017 */ readObject(java.io.ObjectInputStream s)1018 private void readObject(java.io.ObjectInputStream s) 1019 throws java.io.IOException, ClassNotFoundException { 1020 1021 s.defaultReadObject(); 1022 1023 // bind to new lock 1024 resetLock(); 1025 1026 // Read in array length and allocate array 1027 int len = s.readInt(); 1028 SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, len); 1029 Object[] es = new Object[len]; 1030 1031 // Read in all elements in the proper order. 1032 for (int i = 0; i < len; i++) 1033 es[i] = s.readObject(); 1034 setArray(es); 1035 } 1036 1037 /** 1038 * Returns a string representation of this list. The string 1039 * representation consists of the string representations of the list's 1040 * elements in the order they are returned by its iterator, enclosed in 1041 * square brackets ({@code "[]"}). Adjacent elements are separated by 1042 * the characters {@code ", "} (comma and space). Elements are 1043 * converted to strings as by {@link String#valueOf(Object)}. 1044 * 1045 * @return a string representation of this list 1046 */ toString()1047 public String toString() { 1048 return Arrays.toString(getArray()); 1049 } 1050 1051 /** 1052 * Compares the specified object with this list for equality. 1053 * Returns {@code true} if the specified object is the same object 1054 * as this object, or if it is also a {@link List} and the sequence 1055 * of elements returned by an {@linkplain List#iterator() iterator} 1056 * over the specified list is the same as the sequence returned by 1057 * an iterator over this list. The two sequences are considered to 1058 * be the same if they have the same length and corresponding 1059 * elements at the same position in the sequence are <em>equal</em>. 1060 * Two elements {@code e1} and {@code e2} are considered 1061 * <em>equal</em> if {@code Objects.equals(e1, e2)}. 1062 * 1063 * @param o the object to be compared for equality with this list 1064 * @return {@code true} if the specified object is equal to this list 1065 */ equals(Object o)1066 public boolean equals(Object o) { 1067 if (o == this) 1068 return true; 1069 if (!(o instanceof List)) 1070 return false; 1071 1072 List<?> list = (List<?>)o; 1073 Iterator<?> it = list.iterator(); 1074 for (Object element : getArray()) 1075 if (!it.hasNext() || !Objects.equals(element, it.next())) 1076 return false; 1077 return !it.hasNext(); 1078 } 1079 hashCodeOfRange(Object[] es, int from, int to)1080 private static int hashCodeOfRange(Object[] es, int from, int to) { 1081 int hashCode = 1; 1082 for (int i = from; i < to; i++) { 1083 Object x = es[i]; 1084 hashCode = 31 * hashCode + (x == null ? 0 : x.hashCode()); 1085 } 1086 return hashCode; 1087 } 1088 1089 /** 1090 * Returns the hash code value for this list. 1091 * 1092 * <p>This implementation uses the definition in {@link List#hashCode}. 1093 * 1094 * @return the hash code value for this list 1095 */ hashCode()1096 public int hashCode() { 1097 Object[] es = getArray(); 1098 return hashCodeOfRange(es, 0, es.length); 1099 } 1100 1101 /** 1102 * Returns an iterator over the elements in this list in proper sequence. 1103 * 1104 * <p>The returned iterator provides a snapshot of the state of the list 1105 * when the iterator was constructed. No synchronization is needed while 1106 * traversing the iterator. The iterator does <em>NOT</em> support the 1107 * {@code remove} method. 1108 * 1109 * @return an iterator over the elements in this list in proper sequence 1110 */ iterator()1111 public Iterator<E> iterator() { 1112 return new COWIterator<E>(getArray(), 0); 1113 } 1114 1115 /** 1116 * {@inheritDoc} 1117 * 1118 * <p>The returned iterator provides a snapshot of the state of the list 1119 * when the iterator was constructed. No synchronization is needed while 1120 * traversing the iterator. The iterator does <em>NOT</em> support the 1121 * {@code remove}, {@code set} or {@code add} methods. 1122 */ listIterator()1123 public ListIterator<E> listIterator() { 1124 return new COWIterator<E>(getArray(), 0); 1125 } 1126 1127 /** 1128 * {@inheritDoc} 1129 * 1130 * <p>The returned iterator provides a snapshot of the state of the list 1131 * when the iterator was constructed. No synchronization is needed while 1132 * traversing the iterator. The iterator does <em>NOT</em> support the 1133 * {@code remove}, {@code set} or {@code add} methods. 1134 * 1135 * @throws IndexOutOfBoundsException {@inheritDoc} 1136 */ listIterator(int index)1137 public ListIterator<E> listIterator(int index) { 1138 Object[] es = getArray(); 1139 int len = es.length; 1140 if (index < 0 || index > len) 1141 throw new IndexOutOfBoundsException(outOfBounds(index, len)); 1142 1143 return new COWIterator<E>(es, index); 1144 } 1145 1146 /** 1147 * Returns a {@link Spliterator} over the elements in this list. 1148 * 1149 * <p>The {@code Spliterator} reports {@link Spliterator#IMMUTABLE}, 1150 * {@link Spliterator#ORDERED}, {@link Spliterator#SIZED}, and 1151 * {@link Spliterator#SUBSIZED}. 1152 * 1153 * <p>The spliterator provides a snapshot of the state of the list 1154 * when the spliterator was constructed. No synchronization is needed while 1155 * operating on the spliterator. 1156 * 1157 * @return a {@code Spliterator} over the elements in this list 1158 * @since 1.8 1159 */ spliterator()1160 public Spliterator<E> spliterator() { 1161 return Spliterators.spliterator 1162 (getArray(), Spliterator.IMMUTABLE | Spliterator.ORDERED); 1163 } 1164 1165 static final class COWIterator<E> implements ListIterator<E> { 1166 /** Snapshot of the array */ 1167 private final Object[] snapshot; 1168 /** Index of element to be returned by subsequent call to next. */ 1169 private int cursor; 1170 COWIterator(Object[] es, int initialCursor)1171 COWIterator(Object[] es, int initialCursor) { 1172 cursor = initialCursor; 1173 snapshot = es; 1174 } 1175 hasNext()1176 public boolean hasNext() { 1177 return cursor < snapshot.length; 1178 } 1179 hasPrevious()1180 public boolean hasPrevious() { 1181 return cursor > 0; 1182 } 1183 1184 @SuppressWarnings("unchecked") next()1185 public E next() { 1186 if (! hasNext()) 1187 throw new NoSuchElementException(); 1188 return (E) snapshot[cursor++]; 1189 } 1190 1191 @SuppressWarnings("unchecked") previous()1192 public E previous() { 1193 if (! hasPrevious()) 1194 throw new NoSuchElementException(); 1195 return (E) snapshot[--cursor]; 1196 } 1197 nextIndex()1198 public int nextIndex() { 1199 return cursor; 1200 } 1201 previousIndex()1202 public int previousIndex() { 1203 return cursor - 1; 1204 } 1205 1206 /** 1207 * Not supported. Always throws UnsupportedOperationException. 1208 * @throws UnsupportedOperationException always; {@code remove} 1209 * is not supported by this iterator. 1210 */ remove()1211 public void remove() { 1212 throw new UnsupportedOperationException(); 1213 } 1214 1215 /** 1216 * Not supported. Always throws UnsupportedOperationException. 1217 * @throws UnsupportedOperationException always; {@code set} 1218 * is not supported by this iterator. 1219 */ set(E e)1220 public void set(E e) { 1221 throw new UnsupportedOperationException(); 1222 } 1223 1224 /** 1225 * Not supported. Always throws UnsupportedOperationException. 1226 * @throws UnsupportedOperationException always; {@code add} 1227 * is not supported by this iterator. 1228 */ add(E e)1229 public void add(E e) { 1230 throw new UnsupportedOperationException(); 1231 } 1232 1233 @Override forEachRemaining(Consumer<? super E> action)1234 public void forEachRemaining(Consumer<? super E> action) { 1235 Objects.requireNonNull(action); 1236 final int size = snapshot.length; 1237 int i = cursor; 1238 cursor = size; 1239 for (; i < size; i++) 1240 action.accept(elementAt(snapshot, i)); 1241 } 1242 } 1243 1244 /** 1245 * Returns a view of the portion of this list between 1246 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. 1247 * The returned list is backed by this list, so changes in the 1248 * returned list are reflected in this list. 1249 * 1250 * <p>The semantics of the list returned by this method become 1251 * undefined if the backing list (i.e., this list) is modified in 1252 * any way other than via the returned list. 1253 * 1254 * @param fromIndex low endpoint (inclusive) of the subList 1255 * @param toIndex high endpoint (exclusive) of the subList 1256 * @return a view of the specified range within this list 1257 * @throws IndexOutOfBoundsException {@inheritDoc} 1258 */ subList(int fromIndex, int toIndex)1259 public List<E> subList(int fromIndex, int toIndex) { 1260 synchronized (lock) { 1261 Object[] es = getArray(); 1262 int len = es.length; 1263 int size = toIndex - fromIndex; 1264 if (fromIndex < 0 || toIndex > len || size < 0) 1265 throw new IndexOutOfBoundsException(); 1266 return new COWSubList(es, fromIndex, size); 1267 } 1268 } 1269 1270 /** 1271 * Sublist for CopyOnWriteArrayList. 1272 */ 1273 private class COWSubList implements List<E>, RandomAccess { 1274 private final int offset; 1275 private int size; 1276 private Object[] expectedArray; 1277 COWSubList(Object[] es, int offset, int size)1278 COWSubList(Object[] es, int offset, int size) { 1279 // assert Thread.holdsLock(lock); 1280 expectedArray = es; 1281 this.offset = offset; 1282 this.size = size; 1283 } 1284 checkForComodification()1285 private void checkForComodification() { 1286 // assert Thread.holdsLock(lock); 1287 if (getArray() != expectedArray) 1288 throw new ConcurrentModificationException(); 1289 } 1290 getArrayChecked()1291 private Object[] getArrayChecked() { 1292 // assert Thread.holdsLock(lock); 1293 Object[] a = getArray(); 1294 if (a != expectedArray) 1295 throw new ConcurrentModificationException(); 1296 return a; 1297 } 1298 rangeCheck(int index)1299 private void rangeCheck(int index) { 1300 // assert Thread.holdsLock(lock); 1301 if (index < 0 || index >= size) 1302 throw new IndexOutOfBoundsException(outOfBounds(index, size)); 1303 } 1304 rangeCheckForAdd(int index)1305 private void rangeCheckForAdd(int index) { 1306 // assert Thread.holdsLock(lock); 1307 if (index < 0 || index > size) 1308 throw new IndexOutOfBoundsException(outOfBounds(index, size)); 1309 } 1310 toArray()1311 public Object[] toArray() { 1312 final Object[] es; 1313 final int offset; 1314 final int size; 1315 synchronized (lock) { 1316 es = getArrayChecked(); 1317 offset = this.offset; 1318 size = this.size; 1319 } 1320 return Arrays.copyOfRange(es, offset, offset + size); 1321 } 1322 1323 @SuppressWarnings("unchecked") toArray(T[] a)1324 public <T> T[] toArray(T[] a) { 1325 final Object[] es; 1326 final int offset; 1327 final int size; 1328 synchronized (lock) { 1329 es = getArrayChecked(); 1330 offset = this.offset; 1331 size = this.size; 1332 } 1333 if (a.length < size) 1334 return (T[]) Arrays.copyOfRange( 1335 es, offset, offset + size, a.getClass()); 1336 else { 1337 System.arraycopy(es, offset, a, 0, size); 1338 if (a.length > size) 1339 a[size] = null; 1340 return a; 1341 } 1342 } 1343 indexOf(Object o)1344 public int indexOf(Object o) { 1345 final Object[] es; 1346 final int offset; 1347 final int size; 1348 synchronized (lock) { 1349 es = getArrayChecked(); 1350 offset = this.offset; 1351 size = this.size; 1352 } 1353 int i = indexOfRange(o, es, offset, offset + size); 1354 return (i == -1) ? -1 : i - offset; 1355 } 1356 lastIndexOf(Object o)1357 public int lastIndexOf(Object o) { 1358 final Object[] es; 1359 final int offset; 1360 final int size; 1361 synchronized (lock) { 1362 es = getArrayChecked(); 1363 offset = this.offset; 1364 size = this.size; 1365 } 1366 int i = lastIndexOfRange(o, es, offset, offset + size); 1367 return (i == -1) ? -1 : i - offset; 1368 } 1369 contains(Object o)1370 public boolean contains(Object o) { 1371 return indexOf(o) >= 0; 1372 } 1373 containsAll(Collection<?> c)1374 public boolean containsAll(Collection<?> c) { 1375 final Object[] es; 1376 final int offset; 1377 final int size; 1378 synchronized (lock) { 1379 es = getArrayChecked(); 1380 offset = this.offset; 1381 size = this.size; 1382 } 1383 for (Object o : c) 1384 if (indexOfRange(o, es, offset, offset + size) < 0) 1385 return false; 1386 return true; 1387 } 1388 isEmpty()1389 public boolean isEmpty() { 1390 return size() == 0; 1391 } 1392 toString()1393 public String toString() { 1394 return Arrays.toString(toArray()); 1395 } 1396 hashCode()1397 public int hashCode() { 1398 final Object[] es; 1399 final int offset; 1400 final int size; 1401 synchronized (lock) { 1402 es = getArrayChecked(); 1403 offset = this.offset; 1404 size = this.size; 1405 } 1406 return hashCodeOfRange(es, offset, offset + size); 1407 } 1408 equals(Object o)1409 public boolean equals(Object o) { 1410 if (o == this) 1411 return true; 1412 if (!(o instanceof List)) 1413 return false; 1414 Iterator<?> it = ((List<?>)o).iterator(); 1415 1416 final Object[] es; 1417 final int offset; 1418 final int size; 1419 synchronized (lock) { 1420 es = getArrayChecked(); 1421 offset = this.offset; 1422 size = this.size; 1423 } 1424 1425 for (int i = offset, end = offset + size; i < end; i++) 1426 if (!it.hasNext() || !Objects.equals(es[i], it.next())) 1427 return false; 1428 return !it.hasNext(); 1429 } 1430 set(int index, E element)1431 public E set(int index, E element) { 1432 synchronized (lock) { 1433 rangeCheck(index); 1434 checkForComodification(); 1435 E x = CopyOnWriteArrayList.this.set(offset + index, element); 1436 expectedArray = getArray(); 1437 return x; 1438 } 1439 } 1440 get(int index)1441 public E get(int index) { 1442 synchronized (lock) { 1443 rangeCheck(index); 1444 checkForComodification(); 1445 return CopyOnWriteArrayList.this.get(offset + index); 1446 } 1447 } 1448 getFirst()1449 public E getFirst() { 1450 synchronized (lock) { 1451 if (size == 0) 1452 throw new NoSuchElementException(); 1453 else 1454 return get(0); 1455 } 1456 } 1457 getLast()1458 public E getLast() { 1459 synchronized (lock) { 1460 if (size == 0) 1461 throw new NoSuchElementException(); 1462 else 1463 return get(size - 1); 1464 } 1465 } 1466 size()1467 public int size() { 1468 synchronized (lock) { 1469 checkForComodification(); 1470 return size; 1471 } 1472 } 1473 add(E element)1474 public boolean add(E element) { 1475 synchronized (lock) { 1476 checkForComodification(); 1477 CopyOnWriteArrayList.this.add(offset + size, element); 1478 expectedArray = getArray(); 1479 size++; 1480 } 1481 return true; 1482 } 1483 add(int index, E element)1484 public void add(int index, E element) { 1485 synchronized (lock) { 1486 checkForComodification(); 1487 rangeCheckForAdd(index); 1488 CopyOnWriteArrayList.this.add(offset + index, element); 1489 expectedArray = getArray(); 1490 size++; 1491 } 1492 } 1493 addFirst(E e)1494 public void addFirst(E e) { 1495 add(0, e); 1496 } 1497 addLast(E e)1498 public void addLast(E e) { 1499 synchronized (lock) { 1500 add(size, e); 1501 } 1502 } 1503 addAll(Collection<? extends E> c)1504 public boolean addAll(Collection<? extends E> c) { 1505 synchronized (lock) { 1506 final Object[] oldArray = getArrayChecked(); 1507 boolean modified = 1508 CopyOnWriteArrayList.this.addAll(offset + size, c); 1509 size += (expectedArray = getArray()).length - oldArray.length; 1510 return modified; 1511 } 1512 } 1513 addAll(int index, Collection<? extends E> c)1514 public boolean addAll(int index, Collection<? extends E> c) { 1515 synchronized (lock) { 1516 rangeCheckForAdd(index); 1517 final Object[] oldArray = getArrayChecked(); 1518 boolean modified = 1519 CopyOnWriteArrayList.this.addAll(offset + index, c); 1520 size += (expectedArray = getArray()).length - oldArray.length; 1521 return modified; 1522 } 1523 } 1524 clear()1525 public void clear() { 1526 synchronized (lock) { 1527 checkForComodification(); 1528 removeRange(offset, offset + size); 1529 expectedArray = getArray(); 1530 size = 0; 1531 } 1532 } 1533 remove(int index)1534 public E remove(int index) { 1535 synchronized (lock) { 1536 rangeCheck(index); 1537 checkForComodification(); 1538 E result = CopyOnWriteArrayList.this.remove(offset + index); 1539 expectedArray = getArray(); 1540 size--; 1541 return result; 1542 } 1543 } 1544 removeFirst()1545 public E removeFirst() { 1546 synchronized (lock) { 1547 if (size == 0) 1548 throw new NoSuchElementException(); 1549 else 1550 return remove(0); 1551 } 1552 } 1553 removeLast()1554 public E removeLast() { 1555 synchronized (lock) { 1556 if (size == 0) 1557 throw new NoSuchElementException(); 1558 else 1559 return remove(size - 1); 1560 } 1561 } 1562 remove(Object o)1563 public boolean remove(Object o) { 1564 synchronized (lock) { 1565 checkForComodification(); 1566 int index = indexOf(o); 1567 if (index == -1) 1568 return false; 1569 remove(index); 1570 return true; 1571 } 1572 } 1573 iterator()1574 public Iterator<E> iterator() { 1575 return listIterator(0); 1576 } 1577 listIterator()1578 public ListIterator<E> listIterator() { 1579 return listIterator(0); 1580 } 1581 listIterator(int index)1582 public ListIterator<E> listIterator(int index) { 1583 synchronized (lock) { 1584 checkForComodification(); 1585 rangeCheckForAdd(index); 1586 return new COWSubListIterator<E>( 1587 CopyOnWriteArrayList.this, index, offset, size); 1588 } 1589 } 1590 subList(int fromIndex, int toIndex)1591 public List<E> subList(int fromIndex, int toIndex) { 1592 synchronized (lock) { 1593 checkForComodification(); 1594 if (fromIndex < 0 || toIndex > size || fromIndex > toIndex) 1595 throw new IndexOutOfBoundsException(); 1596 return new COWSubList(expectedArray, fromIndex + offset, toIndex - fromIndex); 1597 } 1598 } 1599 forEach(Consumer<? super E> action)1600 public void forEach(Consumer<? super E> action) { 1601 Objects.requireNonNull(action); 1602 int i, end; final Object[] es; 1603 synchronized (lock) { 1604 es = getArrayChecked(); 1605 i = offset; 1606 end = i + size; 1607 } 1608 for (; i < end; i++) 1609 action.accept(elementAt(es, i)); 1610 } 1611 replaceAll(UnaryOperator<E> operator)1612 public void replaceAll(UnaryOperator<E> operator) { 1613 synchronized (lock) { 1614 checkForComodification(); 1615 replaceAllRange(operator, offset, offset + size); 1616 expectedArray = getArray(); 1617 } 1618 } 1619 sort(Comparator<? super E> c)1620 public void sort(Comparator<? super E> c) { 1621 synchronized (lock) { 1622 checkForComodification(); 1623 sortRange(c, offset, offset + size); 1624 expectedArray = getArray(); 1625 } 1626 } 1627 removeAll(Collection<?> c)1628 public boolean removeAll(Collection<?> c) { 1629 Objects.requireNonNull(c); 1630 return bulkRemove(e -> c.contains(e)); 1631 } 1632 retainAll(Collection<?> c)1633 public boolean retainAll(Collection<?> c) { 1634 Objects.requireNonNull(c); 1635 return bulkRemove(e -> !c.contains(e)); 1636 } 1637 removeIf(Predicate<? super E> filter)1638 public boolean removeIf(Predicate<? super E> filter) { 1639 Objects.requireNonNull(filter); 1640 return bulkRemove(filter); 1641 } 1642 bulkRemove(Predicate<? super E> filter)1643 private boolean bulkRemove(Predicate<? super E> filter) { 1644 synchronized (lock) { 1645 final Object[] oldArray = getArrayChecked(); 1646 boolean modified = CopyOnWriteArrayList.this.bulkRemove( 1647 filter, offset, offset + size); 1648 size += (expectedArray = getArray()).length - oldArray.length; 1649 return modified; 1650 } 1651 } 1652 spliterator()1653 public Spliterator<E> spliterator() { 1654 synchronized (lock) { 1655 return Spliterators.spliterator( 1656 getArrayChecked(), offset, offset + size, 1657 Spliterator.IMMUTABLE | Spliterator.ORDERED); 1658 } 1659 } 1660 reversed()1661 public List<E> reversed() { 1662 return new Reversed<>(this, lock); 1663 } 1664 } 1665 1666 private static class COWSubListIterator<E> implements ListIterator<E> { 1667 private final ListIterator<E> it; 1668 private final int offset; 1669 private final int size; 1670 COWSubListIterator(List<E> l, int index, int offset, int size)1671 COWSubListIterator(List<E> l, int index, int offset, int size) { 1672 this.offset = offset; 1673 this.size = size; 1674 it = l.listIterator(index + offset); 1675 } 1676 hasNext()1677 public boolean hasNext() { 1678 return nextIndex() < size; 1679 } 1680 next()1681 public E next() { 1682 if (hasNext()) 1683 return it.next(); 1684 else 1685 throw new NoSuchElementException(); 1686 } 1687 hasPrevious()1688 public boolean hasPrevious() { 1689 return previousIndex() >= 0; 1690 } 1691 previous()1692 public E previous() { 1693 if (hasPrevious()) 1694 return it.previous(); 1695 else 1696 throw new NoSuchElementException(); 1697 } 1698 nextIndex()1699 public int nextIndex() { 1700 return it.nextIndex() - offset; 1701 } 1702 previousIndex()1703 public int previousIndex() { 1704 return it.previousIndex() - offset; 1705 } 1706 remove()1707 public void remove() { 1708 throw new UnsupportedOperationException(); 1709 } 1710 set(E e)1711 public void set(E e) { 1712 throw new UnsupportedOperationException(); 1713 } 1714 add(E e)1715 public void add(E e) { 1716 throw new UnsupportedOperationException(); 1717 } 1718 1719 @Override 1720 @SuppressWarnings("unchecked") forEachRemaining(Consumer<? super E> action)1721 public void forEachRemaining(Consumer<? super E> action) { 1722 Objects.requireNonNull(action); 1723 while (hasNext()) { 1724 action.accept(it.next()); 1725 } 1726 } 1727 } 1728 1729 /** 1730 * {@inheritDoc} 1731 * <p> 1732 * Modifications to the reversed view are permitted and will be propagated 1733 * to this list. In addition, modifications to this list will be visible 1734 * in the reversed view. Sublists and iterators of the reversed view have 1735 * the same restrictions as those of this list. 1736 * 1737 * @since 21 1738 */ reversed()1739 public List<E> reversed() { 1740 return new Reversed<>(this, lock); 1741 } 1742 1743 /** 1744 * Reversed view for CopyOnWriteArrayList and its sublists. 1745 */ 1746 private static class Reversed<E> implements List<E>, RandomAccess { 1747 final List<E> base; 1748 final Object lock; 1749 Reversed(List<E> base, Object lock)1750 Reversed(List<E> base, Object lock) { 1751 this.base = base; 1752 this.lock = lock; 1753 } 1754 1755 class DescendingIterator implements Iterator<E> { 1756 final ListIterator<E> it; DescendingIterator()1757 DescendingIterator() { 1758 synchronized (lock) { 1759 it = base.listIterator(base.size()); 1760 } 1761 } hasNext()1762 public boolean hasNext() { return it.hasPrevious(); } next()1763 public E next() { return it.previous(); } remove()1764 public void remove() { it.remove(); } 1765 } 1766 1767 class DescendingListIterator implements ListIterator<E> { 1768 final ListIterator<E> it; 1769 final int size; // iterator holds a snapshot of the array so this is constant 1770 DescendingListIterator(int pos)1771 DescendingListIterator(int pos) { 1772 synchronized (lock) { 1773 size = base.size(); 1774 if (pos < 0 || pos > size) 1775 throw new IndexOutOfBoundsException(); 1776 it = base.listIterator(size - pos); 1777 } 1778 } 1779 hasNext()1780 public boolean hasNext() { 1781 return it.hasPrevious(); 1782 } 1783 next()1784 public E next() { 1785 return it.previous(); 1786 } 1787 hasPrevious()1788 public boolean hasPrevious() { 1789 return it.hasNext(); 1790 } 1791 previous()1792 public E previous() { 1793 return it.next(); 1794 } 1795 nextIndex()1796 public int nextIndex() { 1797 return size - it.nextIndex(); 1798 } 1799 previousIndex()1800 public int previousIndex() { 1801 return nextIndex() - 1; 1802 } 1803 remove()1804 public void remove() { 1805 throw new UnsupportedOperationException(); 1806 } 1807 set(E e)1808 public void set(E e) { 1809 throw new UnsupportedOperationException(); 1810 } 1811 add(E e)1812 public void add(E e) { 1813 throw new UnsupportedOperationException(); 1814 } 1815 } 1816 1817 // ========== Iterable ========== 1818 forEach(Consumer<? super E> action)1819 public void forEach(Consumer<? super E> action) { 1820 for (E e : this) 1821 action.accept(e); 1822 } 1823 iterator()1824 public Iterator<E> iterator() { 1825 return new DescendingIterator(); 1826 } 1827 spliterator()1828 public Spliterator<E> spliterator() { 1829 return Spliterators.spliterator(this, Spliterator.ORDERED); 1830 } 1831 1832 // ========== Collection ========== 1833 add(E e)1834 public boolean add(E e) { 1835 base.add(0, e); 1836 return true; 1837 } 1838 addAll(Collection<? extends E> c)1839 public boolean addAll(Collection<? extends E> c) { 1840 @SuppressWarnings("unchecked") 1841 E[] es = (E[]) c.toArray(); 1842 if (es.length > 0) { 1843 ArraysSupport.reverse(es); 1844 base.addAll(0, Arrays.asList(es)); 1845 return true; 1846 } else { 1847 return false; 1848 } 1849 } 1850 clear()1851 public void clear() { 1852 base.clear(); 1853 } 1854 contains(Object o)1855 public boolean contains(Object o) { 1856 return base.contains(o); 1857 } 1858 containsAll(Collection<?> c)1859 public boolean containsAll(Collection<?> c) { 1860 return base.containsAll(c); 1861 } 1862 1863 // copied from AbstractList equals(Object o)1864 public boolean equals(Object o) { 1865 if (o == this) 1866 return true; 1867 if (!(o instanceof List)) 1868 return false; 1869 1870 ListIterator<E> e1 = listIterator(); 1871 ListIterator<?> e2 = ((List<?>) o).listIterator(); 1872 while (e1.hasNext() && e2.hasNext()) { 1873 E o1 = e1.next(); 1874 Object o2 = e2.next(); 1875 if (!(o1==null ? o2==null : o1.equals(o2))) 1876 return false; 1877 } 1878 return !(e1.hasNext() || e2.hasNext()); 1879 } 1880 1881 // copied from AbstractList hashCode()1882 public int hashCode() { 1883 int hashCode = 1; 1884 for (E e : this) 1885 hashCode = 31*hashCode + (e==null ? 0 : e.hashCode()); 1886 return hashCode; 1887 } 1888 isEmpty()1889 public boolean isEmpty() { 1890 return base.isEmpty(); 1891 } 1892 parallelStream()1893 public Stream<E> parallelStream() { 1894 return StreamSupport.stream(spliterator(), true); 1895 } 1896 remove(Object o)1897 public boolean remove(Object o) { 1898 synchronized (lock) { 1899 int index = indexOf(o); 1900 if (index == -1) 1901 return false; 1902 remove(index); 1903 return true; 1904 } 1905 } 1906 removeAll(Collection<?> c)1907 public boolean removeAll(Collection<?> c) { 1908 return base.removeAll(c); 1909 } 1910 retainAll(Collection<?> c)1911 public boolean retainAll(Collection<?> c) { 1912 return base.retainAll(c); 1913 } 1914 size()1915 public int size() { 1916 return base.size(); 1917 } 1918 stream()1919 public Stream<E> stream() { 1920 return StreamSupport.stream(spliterator(), false); 1921 } 1922 toArray()1923 public Object[] toArray() { 1924 return ArraysSupport.reverse(base.toArray()); 1925 } 1926 1927 @SuppressWarnings("unchecked") toArray(T[] a)1928 public <T> T[] toArray(T[] a) { 1929 // TODO optimize this 1930 return toArray(i -> (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), i)); 1931 } 1932 toArray(IntFunction<T[]> generator)1933 public <T> T[] toArray(IntFunction<T[]> generator) { 1934 return ArraysSupport.reverse(base.toArray(generator)); 1935 } 1936 1937 // copied from AbstractCollection toString()1938 public String toString() { 1939 Iterator<E> it = iterator(); 1940 if (! it.hasNext()) 1941 return "[]"; 1942 1943 StringBuilder sb = new StringBuilder(); 1944 sb.append('['); 1945 for (;;) { 1946 E e = it.next(); 1947 sb.append(e == this ? "(this Collection)" : e); 1948 if (! it.hasNext()) 1949 return sb.append(']').toString(); 1950 sb.append(',').append(' '); 1951 } 1952 } 1953 1954 // ========== List ========== 1955 add(int index, E element)1956 public void add(int index, E element) { 1957 synchronized (lock) { 1958 base.add(base.size() - index, element); 1959 } 1960 } 1961 addFirst(E e)1962 public void addFirst(E e) { 1963 base.add(e); 1964 } 1965 addLast(E e)1966 public void addLast(E e) { 1967 base.add(0, e); 1968 } 1969 addAll(int index, Collection<? extends E> c)1970 public boolean addAll(int index, Collection<? extends E> c) { 1971 @SuppressWarnings("unchecked") 1972 E[] es = (E[]) c.toArray(); 1973 if (es.length > 0) { 1974 ArraysSupport.reverse(es); 1975 synchronized (lock) { 1976 base.addAll(base.size() - index, Arrays.asList(es)); 1977 } 1978 return true; 1979 } else { 1980 return false; 1981 } 1982 } 1983 get(int i)1984 public E get(int i) { 1985 synchronized (lock) { 1986 return base.get(base.size() - i - 1); 1987 } 1988 } 1989 getFirst()1990 public E getFirst() { 1991 synchronized (lock) { 1992 int size = base.size(); 1993 if (size == 0) 1994 throw new NoSuchElementException(); 1995 else 1996 return base.get(size - 1); 1997 } 1998 } 1999 getLast()2000 public E getLast() { 2001 synchronized (lock) { 2002 if (base.size() == 0) 2003 throw new NoSuchElementException(); 2004 else 2005 return base.get(0); 2006 } 2007 } 2008 indexOf(Object o)2009 public int indexOf(Object o) { 2010 synchronized (lock) { 2011 int i = base.lastIndexOf(o); 2012 return i == -1 ? -1 : base.size() - i - 1; 2013 } 2014 } 2015 lastIndexOf(Object o)2016 public int lastIndexOf(Object o) { 2017 synchronized (lock) { 2018 int i = base.indexOf(o); 2019 return i == -1 ? -1 : base.size() - i - 1; 2020 } 2021 } 2022 listIterator()2023 public ListIterator<E> listIterator() { 2024 return new DescendingListIterator(0); 2025 } 2026 listIterator(int index)2027 public ListIterator<E> listIterator(int index) { 2028 return new DescendingListIterator(index); 2029 } 2030 remove(int index)2031 public E remove(int index) { 2032 synchronized (lock) { 2033 return base.remove(base.size() - index - 1); 2034 } 2035 } 2036 removeFirst()2037 public E removeFirst() { 2038 synchronized (lock) { 2039 int size = base.size(); 2040 if (size == 0) 2041 throw new NoSuchElementException(); 2042 else 2043 return base.remove(size - 1); 2044 } 2045 } 2046 removeLast()2047 public E removeLast() { 2048 synchronized (lock) { 2049 if (base.size() == 0) 2050 throw new NoSuchElementException(); 2051 else 2052 return base.remove(0); 2053 } 2054 } 2055 removeIf(Predicate<? super E> filter)2056 public boolean removeIf(Predicate<? super E> filter) { 2057 return base.removeIf(filter); 2058 } 2059 replaceAll(UnaryOperator<E> operator)2060 public void replaceAll(UnaryOperator<E> operator) { 2061 base.replaceAll(operator); 2062 } 2063 sort(Comparator<? super E> c)2064 public void sort(Comparator<? super E> c) { 2065 base.sort(Collections.reverseOrder(c)); 2066 } 2067 set(int index, E element)2068 public E set(int index, E element) { 2069 synchronized (lock) { 2070 return base.set(base.size() - index - 1, element); 2071 } 2072 } 2073 subList(int fromIndex, int toIndex)2074 public List<E> subList(int fromIndex, int toIndex) { 2075 synchronized (lock) { 2076 int size = base.size(); 2077 var sub = base.subList(size - toIndex, size - fromIndex); 2078 return new Reversed<>(sub, lock); 2079 } 2080 } 2081 reversed()2082 public List<E> reversed() { 2083 return base; 2084 } 2085 } 2086 2087 /** Initializes the lock; for use when deserializing or cloning. */ resetLock()2088 private void resetLock() { 2089 @SuppressWarnings("removal") 2090 Field lockField = java.security.AccessController.doPrivileged( 2091 (java.security.PrivilegedAction<Field>) () -> { 2092 try { 2093 Field f = CopyOnWriteArrayList.class 2094 .getDeclaredField("lock"); 2095 f.setAccessible(true); 2096 return f; 2097 } catch (ReflectiveOperationException e) { 2098 throw new Error(e); 2099 }}); 2100 try { 2101 lockField.set(this, new Object()); 2102 } catch (IllegalAccessException e) { 2103 throw new Error(e); 2104 } 2105 } 2106 } 2107