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