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