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.util.AbstractList; 38 import java.util.Arrays; 39 import java.util.Collection; 40 import java.util.Comparator; 41 import java.util.ConcurrentModificationException; 42 import java.util.Iterator; 43 import java.util.List; 44 import java.util.ListIterator; 45 import java.util.NoSuchElementException; 46 import java.util.Objects; 47 import java.util.RandomAccess; 48 import java.util.Spliterator; 49 import java.util.Spliterators; 50 import java.util.function.Consumer; 51 import java.util.function.Predicate; 52 import java.util.function.UnaryOperator; 53 54 // BEGIN android-note 55 // removed link to collections framework docs 56 // fixed framework docs link to "Collection#optional" 57 // END android-note 58 59 /** 60 * A thread-safe variant of {@link java.util.ArrayList} in which all mutative 61 * operations ({@code add}, {@code set}, and so on) are implemented by 62 * making a fresh copy of the underlying array. 63 * 64 * <p>This is ordinarily too costly, but may be <em>more</em> efficient 65 * than alternatives when traversal operations vastly outnumber 66 * mutations, and is useful when you cannot or don't want to 67 * synchronize traversals, yet need to preclude interference among 68 * concurrent threads. The "snapshot" style iterator method uses a 69 * reference to the state of the array at the point that the iterator 70 * was created. This array never changes during the lifetime of the 71 * iterator, so interference is impossible and the iterator is 72 * guaranteed not to throw {@code ConcurrentModificationException}. 73 * The iterator will not reflect additions, removals, or changes to 74 * the list since the iterator was created. Element-changing 75 * operations on iterators themselves ({@code remove}, {@code set}, and 76 * {@code add}) are not supported. These methods throw 77 * {@code UnsupportedOperationException}. 78 * 79 * <p>All elements are permitted, including {@code null}. 80 * 81 * <p>Memory consistency effects: As with other concurrent 82 * collections, actions in a thread prior to placing an object into a 83 * {@code CopyOnWriteArrayList} 84 * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a> 85 * actions subsequent to the access or removal of that element from 86 * the {@code CopyOnWriteArrayList} in another thread. 87 * 88 * @since 1.5 89 * @author Doug Lea 90 * @param <E> the type of elements held in this list 91 */ 92 public 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 // Android-changed: renamed array -> elements for backwards compatibility b/33916927 104 private transient volatile Object[] elements; 105 106 /** 107 * Gets the array. Non-private so as to also be accessible 108 * from CopyOnWriteArraySet class. 109 */ getArray()110 final Object[] getArray() { 111 return elements; 112 } 113 114 /** 115 * Sets the array. 116 */ setArray(Object[] a)117 final void setArray(Object[] a) { 118 elements = a; 119 } 120 121 /** 122 * Creates an empty list. 123 */ CopyOnWriteArrayList()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 */ CopyOnWriteArrayList(Collection<? extends E> c)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 */ CopyOnWriteArrayList(E[] toCopyIn)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 */ size()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 */ isEmpty()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 */ indexOf(Object o, Object[] elements, int index, int fence)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 */ lastIndexOf(Object o, Object[] elements, int index)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 */ contains(Object o)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 */ indexOf(Object o)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 */ indexOf(E e, int index)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 */ lastIndexOf(Object o)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 */ lastIndexOf(E e, int index)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 */ clone()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 */ toArray()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") toArray(T[] a)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") get(Object[] a, int index)384 private E get(Object[] a, int index) { 385 return (E) a[index]; 386 } 387 outOfBounds(int index, int size)388 static String outOfBounds(int index, int size) { 389 return "Index: " + index + ", Size: " + size; 390 } 391 392 /** 393 * {@inheritDoc} 394 * 395 * @throws IndexOutOfBoundsException {@inheritDoc} 396 */ get(int index)397 public E get(int index) { 398 return get(getArray(), index); 399 } 400 401 /** 402 * Replaces the element at the specified position in this list with the 403 * specified element. 404 * 405 * @throws IndexOutOfBoundsException {@inheritDoc} 406 */ set(int index, E element)407 public E set(int index, E element) { 408 synchronized (lock) { 409 Object[] elements = getArray(); 410 E oldValue = get(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 */ add(E e)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 */ add(int index, E element)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 */ remove(int index)477 public E remove(int index) { 478 synchronized (lock) { 479 Object[] elements = getArray(); 480 int len = elements.length; 481 E oldValue = get(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 */ remove(Object o)508 public boolean remove(Object o) { 509 Object[] snapshot = getArray(); 510 int index = indexOf(o, snapshot, 0, snapshot.length); 511 return (index < 0) ? false : 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 */ remove(Object o, Object[] snapshot, int index)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 */ removeRange(int fromIndex, int toIndex)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 */ addIfAbsent(E e)588 public boolean addIfAbsent(E e) { 589 Object[] snapshot = getArray(); 590 return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false : 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 */ addIfAbsent(E e, Object[] snapshot)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 */ containsAll(Collection<?> c)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="../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="../Collection.html#optional-restrictions">optional</a>), 652 * or if the specified collection is null 653 * @see #remove(Object) 654 */ removeAll(Collection<?> c)655 public boolean removeAll(Collection<?> c) { 656 if (c == null) throw new NullPointerException(); 657 synchronized (lock) { 658 Object[] elements = getArray(); 659 int len = elements.length; 660 if (len != 0) { 661 // temp array holds those elements we know we want to keep 662 int newlen = 0; 663 Object[] temp = new Object[len]; 664 for (int i = 0; i < len; ++i) { 665 Object element = elements[i]; 666 if (!c.contains(element)) 667 temp[newlen++] = element; 668 } 669 if (newlen != len) { 670 setArray(Arrays.copyOf(temp, newlen)); 671 return true; 672 } 673 } 674 return false; 675 } 676 } 677 678 /** 679 * Retains only the elements in this list that are contained in the 680 * specified collection. In other words, removes from this list all of 681 * its elements that are not contained in the specified collection. 682 * 683 * @param c collection containing elements to be retained in this list 684 * @return {@code true} if this list changed as a result of the call 685 * @throws ClassCastException if the class of an element of this list 686 * is incompatible with the specified collection 687 * (<a href="{@docRoot}/../api/java/util/Collection.html#optional-restrictions">optional</a>) 688 * @throws NullPointerException if this list contains a null element and the 689 * specified collection does not permit null elements 690 * (<a href="{@docRoot}/../api/java/util/Collection.html#optional-restrictions">optional</a>), 691 * or if the specified collection is null 692 * @see #remove(Object) 693 */ retainAll(Collection<?> c)694 public boolean retainAll(Collection<?> c) { 695 if (c == null) throw new NullPointerException(); 696 synchronized (lock) { 697 Object[] elements = getArray(); 698 int len = elements.length; 699 if (len != 0) { 700 // temp array holds those elements we know we want to keep 701 int newlen = 0; 702 Object[] temp = new Object[len]; 703 for (int i = 0; i < len; ++i) { 704 Object element = elements[i]; 705 if (c.contains(element)) 706 temp[newlen++] = element; 707 } 708 if (newlen != len) { 709 setArray(Arrays.copyOf(temp, newlen)); 710 return true; 711 } 712 } 713 return false; 714 } 715 } 716 717 /** 718 * Appends all of the elements in the specified collection that 719 * are not already contained in this list, to the end of 720 * this list, in the order that they are returned by the 721 * specified collection's iterator. 722 * 723 * @param c collection containing elements to be added to this list 724 * @return the number of elements added 725 * @throws NullPointerException if the specified collection is null 726 * @see #addIfAbsent(Object) 727 */ addAllAbsent(Collection<? extends E> c)728 public int addAllAbsent(Collection<? extends E> c) { 729 Object[] cs = c.toArray(); 730 if (cs.length == 0) 731 return 0; 732 synchronized (lock) { 733 Object[] elements = getArray(); 734 int len = elements.length; 735 int added = 0; 736 // uniquify and compact elements in cs 737 for (int i = 0; i < cs.length; ++i) { 738 Object e = cs[i]; 739 if (indexOf(e, elements, 0, len) < 0 && 740 indexOf(e, cs, 0, added) < 0) 741 cs[added++] = e; 742 } 743 if (added > 0) { 744 Object[] newElements = Arrays.copyOf(elements, len + added); 745 System.arraycopy(cs, 0, newElements, len, added); 746 setArray(newElements); 747 } 748 return added; 749 } 750 } 751 752 /** 753 * Removes all of the elements from this list. 754 * The list will be empty after this call returns. 755 */ clear()756 public void clear() { 757 synchronized (lock) { 758 setArray(new Object[0]); 759 } 760 } 761 762 /** 763 * Appends all of the elements in the specified collection to the end 764 * of this list, in the order that they are returned by the specified 765 * collection's iterator. 766 * 767 * @param c collection containing elements to be added to this list 768 * @return {@code true} if this list changed as a result of the call 769 * @throws NullPointerException if the specified collection is null 770 * @see #add(Object) 771 */ addAll(Collection<? extends E> c)772 public boolean addAll(Collection<? extends E> c) { 773 Object[] cs = (c.getClass() == CopyOnWriteArrayList.class) ? 774 ((CopyOnWriteArrayList<?>)c).getArray() : c.toArray(); 775 if (cs.length == 0) 776 return false; 777 synchronized (lock) { 778 Object[] elements = getArray(); 779 int len = elements.length; 780 if (len == 0 && cs.getClass() == Object[].class) 781 setArray(cs); 782 else { 783 Object[] newElements = Arrays.copyOf(elements, len + cs.length); 784 System.arraycopy(cs, 0, newElements, len, cs.length); 785 setArray(newElements); 786 } 787 return true; 788 } 789 } 790 791 /** 792 * Inserts all of the elements in the specified collection into this 793 * list, starting at the specified position. Shifts the element 794 * currently at that position (if any) and any subsequent elements to 795 * the right (increases their indices). The new elements will appear 796 * in this list in the order that they are returned by the 797 * specified collection's iterator. 798 * 799 * @param index index at which to insert the first element 800 * from the specified collection 801 * @param c collection containing elements to be added to this list 802 * @return {@code true} if this list changed as a result of the call 803 * @throws IndexOutOfBoundsException {@inheritDoc} 804 * @throws NullPointerException if the specified collection is null 805 * @see #add(int,Object) 806 */ addAll(int index, Collection<? extends E> c)807 public boolean addAll(int index, Collection<? extends E> c) { 808 Object[] cs = c.toArray(); 809 synchronized (lock) { 810 Object[] elements = getArray(); 811 int len = elements.length; 812 if (index > len || index < 0) 813 throw new IndexOutOfBoundsException(outOfBounds(index, len)); 814 if (cs.length == 0) 815 return false; 816 int numMoved = len - index; 817 Object[] newElements; 818 if (numMoved == 0) 819 newElements = Arrays.copyOf(elements, len + cs.length); 820 else { 821 newElements = new Object[len + cs.length]; 822 System.arraycopy(elements, 0, newElements, 0, index); 823 System.arraycopy(elements, index, 824 newElements, index + cs.length, 825 numMoved); 826 } 827 System.arraycopy(cs, 0, newElements, index, cs.length); 828 setArray(newElements); 829 return true; 830 } 831 } 832 forEach(Consumer<? super E> action)833 public void forEach(Consumer<? super E> action) { 834 if (action == null) throw new NullPointerException(); 835 for (Object x : getArray()) { 836 @SuppressWarnings("unchecked") E e = (E) x; 837 action.accept(e); 838 } 839 } 840 removeIf(Predicate<? super E> filter)841 public boolean removeIf(Predicate<? super E> filter) { 842 if (filter == null) throw new NullPointerException(); 843 synchronized (lock) { 844 final Object[] elements = getArray(); 845 final int len = elements.length; 846 int i; 847 for (i = 0; i < len; i++) { 848 @SuppressWarnings("unchecked") E e = (E) elements[i]; 849 if (filter.test(e)) { 850 int newlen = i; 851 final Object[] newElements = new Object[len - 1]; 852 System.arraycopy(elements, 0, newElements, 0, newlen); 853 for (i++; i < len; i++) { 854 @SuppressWarnings("unchecked") E x = (E) elements[i]; 855 if (!filter.test(x)) 856 newElements[newlen++] = x; 857 } 858 setArray((newlen == len - 1) 859 ? newElements // one match => one copy 860 : Arrays.copyOf(newElements, newlen)); 861 return true; 862 } 863 } 864 return false; // zero matches => zero copies 865 } 866 } 867 replaceAll(UnaryOperator<E> operator)868 public void replaceAll(UnaryOperator<E> operator) { 869 if (operator == null) throw new NullPointerException(); 870 synchronized (lock) { 871 Object[] elements = getArray(); 872 int len = elements.length; 873 Object[] newElements = Arrays.copyOf(elements, len); 874 for (int i = 0; i < len; ++i) { 875 @SuppressWarnings("unchecked") E e = (E) elements[i]; 876 newElements[i] = operator.apply(e); 877 } 878 setArray(newElements); 879 } 880 } 881 sort(Comparator<? super E> c)882 public void sort(Comparator<? super E> c) { 883 synchronized (lock) { 884 Object[] elements = getArray(); 885 Object[] newElements = Arrays.copyOf(elements, elements.length); 886 @SuppressWarnings("unchecked") E[] es = (E[])newElements; 887 Arrays.sort(es, c); 888 setArray(newElements); 889 } 890 } 891 892 /** 893 * Saves this list to a stream (that is, serializes it). 894 * 895 * @param s the stream 896 * @throws java.io.IOException if an I/O error occurs 897 * @serialData The length of the array backing the list is emitted 898 * (int), followed by all of its elements (each an Object) 899 * in the proper order. 900 */ writeObject(java.io.ObjectOutputStream s)901 private void writeObject(java.io.ObjectOutputStream s) 902 throws java.io.IOException { 903 904 s.defaultWriteObject(); 905 906 Object[] elements = getArray(); 907 // Write out array length 908 s.writeInt(elements.length); 909 910 // Write out all elements in the proper order. 911 for (Object element : elements) 912 s.writeObject(element); 913 } 914 915 /** 916 * Reconstitutes this list from a stream (that is, deserializes it). 917 * @param s the stream 918 * @throws ClassNotFoundException if the class of a serialized object 919 * could not be found 920 * @throws java.io.IOException if an I/O error occurs 921 */ readObject(java.io.ObjectInputStream s)922 private void readObject(java.io.ObjectInputStream s) 923 throws java.io.IOException, ClassNotFoundException { 924 925 s.defaultReadObject(); 926 927 // bind to new lock 928 resetLock(); 929 930 // Read in array length and allocate array 931 int len = s.readInt(); 932 Object[] elements = new Object[len]; 933 934 // Read in all elements in the proper order. 935 for (int i = 0; i < len; i++) 936 elements[i] = s.readObject(); 937 setArray(elements); 938 } 939 940 /** 941 * Returns a string representation of this list. The string 942 * representation consists of the string representations of the list's 943 * elements in the order they are returned by its iterator, enclosed in 944 * square brackets ({@code "[]"}). Adjacent elements are separated by 945 * the characters {@code ", "} (comma and space). Elements are 946 * converted to strings as by {@link String#valueOf(Object)}. 947 * 948 * @return a string representation of this list 949 */ toString()950 public String toString() { 951 return Arrays.toString(getArray()); 952 } 953 954 /** 955 * Compares the specified object with this list for equality. 956 * Returns {@code true} if the specified object is the same object 957 * as this object, or if it is also a {@link List} and the sequence 958 * of elements returned by an {@linkplain List#iterator() iterator} 959 * over the specified list is the same as the sequence returned by 960 * an iterator over this list. The two sequences are considered to 961 * be the same if they have the same length and corresponding 962 * elements at the same position in the sequence are <em>equal</em>. 963 * Two elements {@code e1} and {@code e2} are considered 964 * <em>equal</em> if {@code Objects.equals(e1, e2)}. 965 * 966 * @param o the object to be compared for equality with this list 967 * @return {@code true} if the specified object is equal to this list 968 */ equals(Object o)969 public boolean equals(Object o) { 970 if (o == this) 971 return true; 972 if (!(o instanceof List)) 973 return false; 974 975 List<?> list = (List<?>)o; 976 Iterator<?> it = list.iterator(); 977 Object[] elements = getArray(); 978 for (int i = 0, len = elements.length; i < len; i++) 979 if (!it.hasNext() || !Objects.equals(elements[i], it.next())) 980 return false; 981 if (it.hasNext()) 982 return false; 983 return true; 984 } 985 986 /** 987 * Returns the hash code value for this list. 988 * 989 * <p>This implementation uses the definition in {@link List#hashCode}. 990 * 991 * @return the hash code value for this list 992 */ hashCode()993 public int hashCode() { 994 int hashCode = 1; 995 for (Object x : getArray()) 996 hashCode = 31 * hashCode + (x == null ? 0 : x.hashCode()); 997 return hashCode; 998 } 999 1000 /** 1001 * Returns an iterator over the elements in this list in proper sequence. 1002 * 1003 * <p>The returned iterator provides a snapshot of the state of the list 1004 * when the iterator was constructed. No synchronization is needed while 1005 * traversing the iterator. The iterator does <em>NOT</em> support the 1006 * {@code remove} method. 1007 * 1008 * @return an iterator over the elements in this list in proper sequence 1009 */ iterator()1010 public Iterator<E> iterator() { 1011 return new COWIterator<E>(getArray(), 0); 1012 } 1013 1014 /** 1015 * {@inheritDoc} 1016 * 1017 * <p>The returned iterator provides a snapshot of the state of the list 1018 * when the iterator was constructed. No synchronization is needed while 1019 * traversing the iterator. The iterator does <em>NOT</em> support the 1020 * {@code remove}, {@code set} or {@code add} methods. 1021 */ listIterator()1022 public ListIterator<E> listIterator() { 1023 return new COWIterator<E>(getArray(), 0); 1024 } 1025 1026 /** 1027 * {@inheritDoc} 1028 * 1029 * <p>The returned iterator provides a snapshot of the state of the list 1030 * when the iterator was constructed. No synchronization is needed while 1031 * traversing the iterator. The iterator does <em>NOT</em> support the 1032 * {@code remove}, {@code set} or {@code add} methods. 1033 * 1034 * @throws IndexOutOfBoundsException {@inheritDoc} 1035 */ listIterator(int index)1036 public ListIterator<E> listIterator(int index) { 1037 Object[] elements = getArray(); 1038 int len = elements.length; 1039 if (index < 0 || index > len) 1040 throw new IndexOutOfBoundsException(outOfBounds(index, len)); 1041 1042 return new COWIterator<E>(elements, index); 1043 } 1044 1045 /** 1046 * Returns a {@link Spliterator} over the elements in this list. 1047 * 1048 * <p>The {@code Spliterator} reports {@link Spliterator#IMMUTABLE}, 1049 * {@link Spliterator#ORDERED}, {@link Spliterator#SIZED}, and 1050 * {@link Spliterator#SUBSIZED}. 1051 * 1052 * <p>The spliterator provides a snapshot of the state of the list 1053 * when the spliterator was constructed. No synchronization is needed while 1054 * operating on the spliterator. 1055 * 1056 * @return a {@code Spliterator} over the elements in this list 1057 * @since 1.8 1058 */ spliterator()1059 public Spliterator<E> spliterator() { 1060 return Spliterators.spliterator 1061 (getArray(), Spliterator.IMMUTABLE | Spliterator.ORDERED); 1062 } 1063 1064 static final class COWIterator<E> implements ListIterator<E> { 1065 /** Snapshot of the array */ 1066 private final Object[] snapshot; 1067 /** Index of element to be returned by subsequent call to next. */ 1068 private int cursor; 1069 COWIterator(Object[] elements, int initialCursor)1070 COWIterator(Object[] elements, int initialCursor) { 1071 cursor = initialCursor; 1072 snapshot = elements; 1073 } 1074 hasNext()1075 public boolean hasNext() { 1076 return cursor < snapshot.length; 1077 } 1078 hasPrevious()1079 public boolean hasPrevious() { 1080 return cursor > 0; 1081 } 1082 1083 @SuppressWarnings("unchecked") next()1084 public E next() { 1085 if (! hasNext()) 1086 throw new NoSuchElementException(); 1087 return (E) snapshot[cursor++]; 1088 } 1089 1090 @SuppressWarnings("unchecked") previous()1091 public E previous() { 1092 if (! hasPrevious()) 1093 throw new NoSuchElementException(); 1094 return (E) snapshot[--cursor]; 1095 } 1096 nextIndex()1097 public int nextIndex() { 1098 return cursor; 1099 } 1100 previousIndex()1101 public int previousIndex() { 1102 return cursor-1; 1103 } 1104 1105 /** 1106 * Not supported. Always throws UnsupportedOperationException. 1107 * @throws UnsupportedOperationException always; {@code remove} 1108 * is not supported by this iterator. 1109 */ remove()1110 public void remove() { 1111 throw new UnsupportedOperationException(); 1112 } 1113 1114 /** 1115 * Not supported. Always throws UnsupportedOperationException. 1116 * @throws UnsupportedOperationException always; {@code set} 1117 * is not supported by this iterator. 1118 */ set(E e)1119 public void set(E e) { 1120 throw new UnsupportedOperationException(); 1121 } 1122 1123 /** 1124 * Not supported. Always throws UnsupportedOperationException. 1125 * @throws UnsupportedOperationException always; {@code add} 1126 * is not supported by this iterator. 1127 */ add(E e)1128 public void add(E e) { 1129 throw new UnsupportedOperationException(); 1130 } 1131 1132 @Override 1133 @SuppressWarnings("unchecked") forEachRemaining(Consumer<? super E> action)1134 public void forEachRemaining(Consumer<? super E> action) { 1135 Objects.requireNonNull(action); 1136 final int size = snapshot.length; 1137 for (int i = cursor; i < size; i++) { 1138 action.accept((E) snapshot[i]); 1139 } 1140 cursor = size; 1141 } 1142 } 1143 1144 /** 1145 * Returns a view of the portion of this list between 1146 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. 1147 * The returned list is backed by this list, so changes in the 1148 * returned list are reflected in this list. 1149 * 1150 * <p>The semantics of the list returned by this method become 1151 * undefined if the backing list (i.e., this list) is modified in 1152 * any way other than via the returned list. 1153 * 1154 * @param fromIndex low endpoint (inclusive) of the subList 1155 * @param toIndex high endpoint (exclusive) of the subList 1156 * @return a view of the specified range within this list 1157 * @throws IndexOutOfBoundsException {@inheritDoc} 1158 */ subList(int fromIndex, int toIndex)1159 public List<E> subList(int fromIndex, int toIndex) { 1160 synchronized (lock) { 1161 Object[] elements = getArray(); 1162 int len = elements.length; 1163 if (fromIndex < 0 || toIndex > len || fromIndex > toIndex) 1164 throw new IndexOutOfBoundsException(); 1165 return new COWSubList<E>(this, fromIndex, toIndex); 1166 } 1167 } 1168 1169 /** 1170 * Sublist for CopyOnWriteArrayList. 1171 * This class extends AbstractList merely for convenience, to 1172 * avoid having to define addAll, etc. This doesn't hurt, but 1173 * is wasteful. This class does not need or use modCount 1174 * mechanics in AbstractList, but does need to check for 1175 * concurrent modification using similar mechanics. On each 1176 * operation, the array that we expect the backing list to use 1177 * is checked and updated. Since we do this for all of the 1178 * base operations invoked by those defined in AbstractList, 1179 * all is well. While inefficient, this is not worth 1180 * improving. The kinds of list operations inherited from 1181 * AbstractList are already so slow on COW sublists that 1182 * adding a bit more space/time doesn't seem even noticeable. 1183 */ 1184 private static class COWSubList<E> 1185 extends AbstractList<E> 1186 implements RandomAccess 1187 { 1188 private final CopyOnWriteArrayList<E> l; 1189 private final int offset; 1190 private int size; 1191 private Object[] expectedArray; 1192 1193 // only call this holding l's lock COWSubList(CopyOnWriteArrayList<E> list, int fromIndex, int toIndex)1194 COWSubList(CopyOnWriteArrayList<E> list, 1195 int fromIndex, int toIndex) { 1196 // assert Thread.holdsLock(list.lock); 1197 l = list; 1198 expectedArray = l.getArray(); 1199 offset = fromIndex; 1200 size = toIndex - fromIndex; 1201 } 1202 1203 // only call this holding l's lock checkForComodification()1204 private void checkForComodification() { 1205 // assert Thread.holdsLock(l.lock); 1206 if (l.getArray() != expectedArray) 1207 throw new ConcurrentModificationException(); 1208 } 1209 1210 // only call this holding l's lock rangeCheck(int index)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 set(int index, E element)1217 public E set(int index, E element) { 1218 synchronized (l.lock) { 1219 rangeCheck(index); 1220 checkForComodification(); 1221 E x = l.set(index+offset, element); 1222 expectedArray = l.getArray(); 1223 return x; 1224 } 1225 } 1226 get(int index)1227 public E get(int index) { 1228 synchronized (l.lock) { 1229 rangeCheck(index); 1230 checkForComodification(); 1231 return l.get(index+offset); 1232 } 1233 } 1234 size()1235 public int size() { 1236 synchronized (l.lock) { 1237 checkForComodification(); 1238 return size; 1239 } 1240 } 1241 add(int index, E element)1242 public void add(int index, E element) { 1243 synchronized (l.lock) { 1244 checkForComodification(); 1245 if (index < 0 || index > size) 1246 throw new IndexOutOfBoundsException 1247 (outOfBounds(index, size)); 1248 l.add(index+offset, element); 1249 expectedArray = l.getArray(); 1250 size++; 1251 } 1252 } 1253 clear()1254 public void clear() { 1255 synchronized (l.lock) { 1256 checkForComodification(); 1257 l.removeRange(offset, offset+size); 1258 expectedArray = l.getArray(); 1259 size = 0; 1260 } 1261 } 1262 remove(int index)1263 public E remove(int index) { 1264 synchronized (l.lock) { 1265 rangeCheck(index); 1266 checkForComodification(); 1267 E result = l.remove(index+offset); 1268 expectedArray = l.getArray(); 1269 size--; 1270 return result; 1271 } 1272 } 1273 remove(Object o)1274 public boolean remove(Object o) { 1275 int index = indexOf(o); 1276 if (index == -1) 1277 return false; 1278 remove(index); 1279 return true; 1280 } 1281 iterator()1282 public Iterator<E> iterator() { 1283 synchronized (l.lock) { 1284 checkForComodification(); 1285 return new COWSubListIterator<E>(l, 0, offset, size); 1286 } 1287 } 1288 listIterator(int index)1289 public ListIterator<E> listIterator(int index) { 1290 synchronized (l.lock) { 1291 checkForComodification(); 1292 if (index < 0 || index > size) 1293 throw new IndexOutOfBoundsException 1294 (outOfBounds(index, size)); 1295 return new COWSubListIterator<E>(l, index, offset, size); 1296 } 1297 } 1298 subList(int fromIndex, int toIndex)1299 public List<E> subList(int fromIndex, int toIndex) { 1300 synchronized (l.lock) { 1301 checkForComodification(); 1302 if (fromIndex < 0 || toIndex > size || fromIndex > toIndex) 1303 throw new IndexOutOfBoundsException(); 1304 return new COWSubList<E>(l, fromIndex + offset, 1305 toIndex + offset); 1306 } 1307 } 1308 forEach(Consumer<? super E> action)1309 public void forEach(Consumer<? super E> action) { 1310 if (action == null) throw new NullPointerException(); 1311 int lo = offset; 1312 int hi = offset + size; 1313 Object[] a = expectedArray; 1314 if (l.getArray() != a) 1315 throw new ConcurrentModificationException(); 1316 if (lo < 0 || hi > a.length) 1317 throw new IndexOutOfBoundsException(); 1318 for (int i = lo; i < hi; ++i) { 1319 @SuppressWarnings("unchecked") E e = (E) a[i]; 1320 action.accept(e); 1321 } 1322 } 1323 replaceAll(UnaryOperator<E> operator)1324 public void replaceAll(UnaryOperator<E> operator) { 1325 if (operator == null) throw new NullPointerException(); 1326 synchronized (l.lock) { 1327 int lo = offset; 1328 int hi = offset + size; 1329 Object[] elements = expectedArray; 1330 if (l.getArray() != elements) 1331 throw new ConcurrentModificationException(); 1332 int len = elements.length; 1333 if (lo < 0 || hi > len) 1334 throw new IndexOutOfBoundsException(); 1335 Object[] newElements = Arrays.copyOf(elements, len); 1336 for (int i = lo; i < hi; ++i) { 1337 @SuppressWarnings("unchecked") E e = (E) elements[i]; 1338 newElements[i] = operator.apply(e); 1339 } 1340 l.setArray(expectedArray = newElements); 1341 } 1342 } 1343 sort(Comparator<? super E> c)1344 public void sort(Comparator<? super E> c) { 1345 synchronized (l.lock) { 1346 int lo = offset; 1347 int hi = offset + size; 1348 Object[] elements = expectedArray; 1349 if (l.getArray() != elements) 1350 throw new ConcurrentModificationException(); 1351 int len = elements.length; 1352 if (lo < 0 || hi > len) 1353 throw new IndexOutOfBoundsException(); 1354 Object[] newElements = Arrays.copyOf(elements, len); 1355 @SuppressWarnings("unchecked") E[] es = (E[])newElements; 1356 Arrays.sort(es, lo, hi, c); 1357 l.setArray(expectedArray = newElements); 1358 } 1359 } 1360 removeAll(Collection<?> c)1361 public boolean removeAll(Collection<?> c) { 1362 if (c == null) throw new NullPointerException(); 1363 boolean removed = false; 1364 synchronized (l.lock) { 1365 int n = size; 1366 if (n > 0) { 1367 int lo = offset; 1368 int hi = offset + n; 1369 Object[] elements = expectedArray; 1370 if (l.getArray() != elements) 1371 throw new ConcurrentModificationException(); 1372 int len = elements.length; 1373 if (lo < 0 || hi > len) 1374 throw new IndexOutOfBoundsException(); 1375 int newSize = 0; 1376 Object[] temp = new Object[n]; 1377 for (int i = lo; i < hi; ++i) { 1378 Object element = elements[i]; 1379 if (!c.contains(element)) 1380 temp[newSize++] = element; 1381 } 1382 if (newSize != n) { 1383 Object[] newElements = new Object[len - n + newSize]; 1384 System.arraycopy(elements, 0, newElements, 0, lo); 1385 System.arraycopy(temp, 0, newElements, lo, newSize); 1386 System.arraycopy(elements, hi, newElements, 1387 lo + newSize, len - hi); 1388 size = newSize; 1389 removed = true; 1390 l.setArray(expectedArray = newElements); 1391 } 1392 } 1393 } 1394 return removed; 1395 } 1396 retainAll(Collection<?> c)1397 public boolean retainAll(Collection<?> c) { 1398 if (c == null) throw new NullPointerException(); 1399 boolean removed = false; 1400 synchronized (l.lock) { 1401 int n = size; 1402 if (n > 0) { 1403 int lo = offset; 1404 int hi = offset + n; 1405 Object[] elements = expectedArray; 1406 if (l.getArray() != elements) 1407 throw new ConcurrentModificationException(); 1408 int len = elements.length; 1409 if (lo < 0 || hi > len) 1410 throw new IndexOutOfBoundsException(); 1411 int newSize = 0; 1412 Object[] temp = new Object[n]; 1413 for (int i = lo; i < hi; ++i) { 1414 Object element = elements[i]; 1415 if (c.contains(element)) 1416 temp[newSize++] = element; 1417 } 1418 if (newSize != n) { 1419 Object[] newElements = new Object[len - n + newSize]; 1420 System.arraycopy(elements, 0, newElements, 0, lo); 1421 System.arraycopy(temp, 0, newElements, lo, newSize); 1422 System.arraycopy(elements, hi, newElements, 1423 lo + newSize, len - hi); 1424 size = newSize; 1425 removed = true; 1426 l.setArray(expectedArray = newElements); 1427 } 1428 } 1429 } 1430 return removed; 1431 } 1432 removeIf(Predicate<? super E> filter)1433 public boolean removeIf(Predicate<? super E> filter) { 1434 if (filter == null) throw new NullPointerException(); 1435 boolean removed = false; 1436 synchronized (l.lock) { 1437 int n = size; 1438 if (n > 0) { 1439 int lo = offset; 1440 int hi = offset + n; 1441 Object[] elements = expectedArray; 1442 if (l.getArray() != elements) 1443 throw new ConcurrentModificationException(); 1444 int len = elements.length; 1445 if (lo < 0 || hi > len) 1446 throw new IndexOutOfBoundsException(); 1447 int newSize = 0; 1448 Object[] temp = new Object[n]; 1449 for (int i = lo; i < hi; ++i) { 1450 @SuppressWarnings("unchecked") E e = (E) elements[i]; 1451 if (!filter.test(e)) 1452 temp[newSize++] = e; 1453 } 1454 if (newSize != n) { 1455 Object[] newElements = new Object[len - n + newSize]; 1456 System.arraycopy(elements, 0, newElements, 0, lo); 1457 System.arraycopy(temp, 0, newElements, lo, newSize); 1458 System.arraycopy(elements, hi, newElements, 1459 lo + newSize, len - hi); 1460 size = newSize; 1461 removed = true; 1462 l.setArray(expectedArray = newElements); 1463 } 1464 } 1465 } 1466 return removed; 1467 } 1468 spliterator()1469 public Spliterator<E> spliterator() { 1470 int lo = offset; 1471 int hi = offset + size; 1472 Object[] a = expectedArray; 1473 if (l.getArray() != a) 1474 throw new ConcurrentModificationException(); 1475 if (lo < 0 || hi > a.length) 1476 throw new IndexOutOfBoundsException(); 1477 return Spliterators.spliterator 1478 (a, lo, hi, Spliterator.IMMUTABLE | Spliterator.ORDERED); 1479 } 1480 1481 } 1482 1483 private static class COWSubListIterator<E> implements ListIterator<E> { 1484 private final ListIterator<E> it; 1485 private final int offset; 1486 private final int size; 1487 COWSubListIterator(List<E> l, int index, int offset, int size)1488 COWSubListIterator(List<E> l, int index, int offset, int size) { 1489 this.offset = offset; 1490 this.size = size; 1491 it = l.listIterator(index+offset); 1492 } 1493 hasNext()1494 public boolean hasNext() { 1495 return nextIndex() < size; 1496 } 1497 next()1498 public E next() { 1499 if (hasNext()) 1500 return it.next(); 1501 else 1502 throw new NoSuchElementException(); 1503 } 1504 hasPrevious()1505 public boolean hasPrevious() { 1506 return previousIndex() >= 0; 1507 } 1508 previous()1509 public E previous() { 1510 if (hasPrevious()) 1511 return it.previous(); 1512 else 1513 throw new NoSuchElementException(); 1514 } 1515 nextIndex()1516 public int nextIndex() { 1517 return it.nextIndex() - offset; 1518 } 1519 previousIndex()1520 public int previousIndex() { 1521 return it.previousIndex() - offset; 1522 } 1523 remove()1524 public void remove() { 1525 throw new UnsupportedOperationException(); 1526 } 1527 set(E e)1528 public void set(E e) { 1529 throw new UnsupportedOperationException(); 1530 } 1531 add(E e)1532 public void add(E e) { 1533 throw new UnsupportedOperationException(); 1534 } 1535 1536 @Override 1537 @SuppressWarnings("unchecked") forEachRemaining(Consumer<? super E> action)1538 public void forEachRemaining(Consumer<? super E> action) { 1539 Objects.requireNonNull(action); 1540 while (nextIndex() < size) { 1541 action.accept(it.next()); 1542 } 1543 } 1544 } 1545 1546 // Support for resetting lock while deserializing resetLock()1547 private void resetLock() { 1548 U.putObjectVolatile(this, LOCK, new Object()); 1549 } 1550 private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe(); 1551 private static final long LOCK; 1552 static { 1553 try { 1554 LOCK = U.objectFieldOffset 1555 (CopyOnWriteArrayList.class.getDeclaredField("lock")); 1556 } catch (ReflectiveOperationException e) { 1557 throw new Error(e); 1558 } 1559 } 1560 } 1561