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