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