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 54 /** 55 * A thread-safe variant of {@link java.util.ArrayList} in which all mutative 56 * operations ({@code add}, {@code set}, and so on) are implemented by 57 * making a fresh copy of the underlying array. 58 * 59 * <p>This is ordinarily too costly, but may be <em>more</em> efficient 60 * than alternatives when traversal operations vastly outnumber 61 * mutations, and is useful when you cannot or don't want to 62 * synchronize traversals, yet need to preclude interference among 63 * concurrent threads. The "snapshot" style iterator method uses a 64 * reference to the state of the array at the point that the iterator 65 * was created. This array never changes during the lifetime of the 66 * iterator, so interference is impossible and the iterator is 67 * guaranteed not to throw {@code ConcurrentModificationException}. 68 * The iterator will not reflect additions, removals, or changes to 69 * the list since the iterator was created. Element-changing 70 * operations on iterators themselves ({@code remove}, {@code set}, and 71 * {@code add}) are not supported. These methods throw 72 * {@code UnsupportedOperationException}. 73 * 74 * <p>All elements are permitted, including {@code null}. 75 * 76 * <p>Memory consistency effects: As with other concurrent 77 * collections, actions in a thread prior to placing an object into a 78 * {@code CopyOnWriteArrayList} 79 * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a> 80 * actions subsequent to the access or removal of that element from 81 * the {@code CopyOnWriteArrayList} in another thread. 82 * 83 * <p>This class is a member of the 84 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 85 * Java Collections Framework</a>. 86 * 87 * @since 1.5 88 * @author Doug Lea 89 * @param <E> the type of elements held in this collection 90 */ 91 public class CopyOnWriteArrayList<E> 92 implements List<E>, RandomAccess, Cloneable, java.io.Serializable { 93 private static final long serialVersionUID = 8673264195747942595L; 94 95 /** The lock protecting all mutators */ 96 final transient ReentrantLock lock = new ReentrantLock(); 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 */ 105 final Object[] getArray() { 106 return array; 107 } 108 109 /** 110 * Sets the array. 111 */ 112 final void setArray(Object[] a) { 113 array = a; 114 } 115 116 /** 117 * Creates an empty list. 118 */ 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 */ 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 */ 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 Object[] elements = new Object[len]; 994 995 // Read in all elements in the proper order. 996 for (int i = 0; i < len; i++) 997 elements[i] = s.readObject(); 998 setArray(elements); 999 } 1000 1001 /** 1002 * Returns a string representation of this list. The string 1003 * representation consists of the string representations of the list's 1004 * elements in the order they are returned by its iterator, enclosed in 1005 * square brackets ({@code "[]"}). Adjacent elements are separated by 1006 * the characters {@code ", "} (comma and space). Elements are 1007 * converted to strings as by {@link String#valueOf(Object)}. 1008 * 1009 * @return a string representation of this list 1010 */ 1011 public String toString() { 1012 return Arrays.toString(getArray()); 1013 } 1014 1015 /** 1016 * Compares the specified object with this list for equality. 1017 * Returns {@code true} if the specified object is the same object 1018 * as this object, or if it is also a {@link List} and the sequence 1019 * of elements returned by an {@linkplain List#iterator() iterator} 1020 * over the specified list is the same as the sequence returned by 1021 * an iterator over this list. The two sequences are considered to 1022 * be the same if they have the same length and corresponding 1023 * elements at the same position in the sequence are <em>equal</em>. 1024 * Two elements {@code e1} and {@code e2} are considered 1025 * <em>equal</em> if {@code (e1==null ? e2==null : e1.equals(e2))}. 1026 * 1027 * @param o the object to be compared for equality with this list 1028 * @return {@code true} if the specified object is equal to this list 1029 */ 1030 public boolean equals(Object o) { 1031 if (o == this) 1032 return true; 1033 if (!(o instanceof List)) 1034 return false; 1035 1036 List<?> list = (List<?>)(o); 1037 Iterator<?> it = list.iterator(); 1038 Object[] elements = getArray(); 1039 int len = elements.length; 1040 for (int i = 0; i < len; ++i) 1041 if (!it.hasNext() || !eq(elements[i], it.next())) 1042 return false; 1043 if (it.hasNext()) 1044 return false; 1045 return true; 1046 } 1047 1048 /** 1049 * Returns the hash code value for this list. 1050 * 1051 * <p>This implementation uses the definition in {@link List#hashCode}. 1052 * 1053 * @return the hash code value for this list 1054 */ 1055 public int hashCode() { 1056 int hashCode = 1; 1057 Object[] elements = getArray(); 1058 int len = elements.length; 1059 for (int i = 0; i < len; ++i) { 1060 Object obj = elements[i]; 1061 hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode()); 1062 } 1063 return hashCode; 1064 } 1065 1066 /** 1067 * Returns an iterator over the elements in this list in proper sequence. 1068 * 1069 * <p>The returned iterator provides a snapshot of the state of the list 1070 * when the iterator was constructed. No synchronization is needed while 1071 * traversing the iterator. The iterator does <em>NOT</em> support the 1072 * {@code remove} method. 1073 * 1074 * @return an iterator over the elements in this list in proper sequence 1075 */ 1076 public Iterator<E> iterator() { 1077 return new COWIterator<E>(getArray(), 0); 1078 } 1079 1080 /** 1081 * {@inheritDoc} 1082 * 1083 * <p>The returned iterator provides a snapshot of the state of the list 1084 * when the iterator was constructed. No synchronization is needed while 1085 * traversing the iterator. The iterator does <em>NOT</em> support the 1086 * {@code remove}, {@code set} or {@code add} methods. 1087 */ 1088 public ListIterator<E> listIterator() { 1089 return new COWIterator<E>(getArray(), 0); 1090 } 1091 1092 /** 1093 * {@inheritDoc} 1094 * 1095 * <p>The returned iterator provides a snapshot of the state of the list 1096 * when the iterator was constructed. No synchronization is needed while 1097 * traversing the iterator. The iterator does <em>NOT</em> support the 1098 * {@code remove}, {@code set} or {@code add} methods. 1099 * 1100 * @throws IndexOutOfBoundsException {@inheritDoc} 1101 */ 1102 public ListIterator<E> listIterator(int index) { 1103 Object[] elements = getArray(); 1104 int len = elements.length; 1105 if (index < 0 || index > len) 1106 throw new IndexOutOfBoundsException("Index: "+index); 1107 1108 return new COWIterator<E>(elements, index); 1109 } 1110 1111 /** 1112 * Returns a {@link Spliterator} over the elements in this list. 1113 * 1114 * <p>The {@code Spliterator} reports {@link Spliterator#IMMUTABLE}, 1115 * {@link Spliterator#ORDERED}, {@link Spliterator#SIZED}, and 1116 * {@link Spliterator#SUBSIZED}. 1117 * 1118 * <p>The spliterator provides a snapshot of the state of the list 1119 * when the spliterator was constructed. No synchronization is needed while 1120 * operating on the spliterator. 1121 * 1122 * @return a {@code Spliterator} over the elements in this list 1123 * @since 1.8 1124 */ 1125 public Spliterator<E> spliterator() { 1126 return Spliterators.spliterator 1127 (getArray(), Spliterator.IMMUTABLE | Spliterator.ORDERED); 1128 } 1129 1130 static final class COWIterator<E> implements ListIterator<E> { 1131 /** Snapshot of the array */ 1132 private final Object[] snapshot; 1133 /** Index of element to be returned by subsequent call to next. */ 1134 private int cursor; 1135 1136 private COWIterator(Object[] elements, int initialCursor) { 1137 cursor = initialCursor; 1138 snapshot = elements; 1139 } 1140 1141 public boolean hasNext() { 1142 return cursor < snapshot.length; 1143 } 1144 1145 public boolean hasPrevious() { 1146 return cursor > 0; 1147 } 1148 1149 @SuppressWarnings("unchecked") 1150 public E next() { 1151 if (! hasNext()) 1152 throw new NoSuchElementException(); 1153 return (E) snapshot[cursor++]; 1154 } 1155 1156 @SuppressWarnings("unchecked") 1157 public E previous() { 1158 if (! hasPrevious()) 1159 throw new NoSuchElementException(); 1160 return (E) snapshot[--cursor]; 1161 } 1162 1163 public int nextIndex() { 1164 return cursor; 1165 } 1166 1167 public int previousIndex() { 1168 return cursor-1; 1169 } 1170 1171 /** 1172 * Not supported. Always throws UnsupportedOperationException. 1173 * @throws UnsupportedOperationException always; {@code remove} 1174 * is not supported by this iterator. 1175 */ 1176 public void remove() { 1177 throw new UnsupportedOperationException(); 1178 } 1179 1180 /** 1181 * Not supported. Always throws UnsupportedOperationException. 1182 * @throws UnsupportedOperationException always; {@code set} 1183 * is not supported by this iterator. 1184 */ 1185 public void set(E e) { 1186 throw new UnsupportedOperationException(); 1187 } 1188 1189 /** 1190 * Not supported. Always throws UnsupportedOperationException. 1191 * @throws UnsupportedOperationException always; {@code add} 1192 * is not supported by this iterator. 1193 */ 1194 public void add(E e) { 1195 throw new UnsupportedOperationException(); 1196 } 1197 1198 @Override 1199 public void forEachRemaining(Consumer<? super E> action) { 1200 Objects.requireNonNull(action); 1201 Object[] elements = snapshot; 1202 final int size = elements.length; 1203 for (int i = cursor; i < size; i++) { 1204 @SuppressWarnings("unchecked") E e = (E) elements[i]; 1205 action.accept(e); 1206 } 1207 cursor = size; 1208 } 1209 } 1210 1211 /** 1212 * Returns a view of the portion of this list between 1213 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. 1214 * The returned list is backed by this list, so changes in the 1215 * returned list are reflected in this list. 1216 * 1217 * <p>The semantics of the list returned by this method become 1218 * undefined if the backing list (i.e., this list) is modified in 1219 * any way other than via the returned list. 1220 * 1221 * @param fromIndex low endpoint (inclusive) of the subList 1222 * @param toIndex high endpoint (exclusive) of the subList 1223 * @return a view of the specified range within this list 1224 * @throws IndexOutOfBoundsException {@inheritDoc} 1225 */ 1226 public List<E> subList(int fromIndex, int toIndex) { 1227 final ReentrantLock lock = this.lock; 1228 lock.lock(); 1229 try { 1230 Object[] elements = getArray(); 1231 int len = elements.length; 1232 if (fromIndex < 0 || toIndex > len || fromIndex > toIndex) 1233 throw new IndexOutOfBoundsException(); 1234 return new COWSubList<E>(this, fromIndex, toIndex); 1235 } finally { 1236 lock.unlock(); 1237 } 1238 } 1239 1240 /** 1241 * Sublist for CopyOnWriteArrayList. 1242 * This class extends AbstractList merely for convenience, to 1243 * avoid having to define addAll, etc. This doesn't hurt, but 1244 * is wasteful. This class does not need or use modCount 1245 * mechanics in AbstractList, but does need to check for 1246 * concurrent modification using similar mechanics. On each 1247 * operation, the array that we expect the backing list to use 1248 * is checked and updated. Since we do this for all of the 1249 * base operations invoked by those defined in AbstractList, 1250 * all is well. While inefficient, this is not worth 1251 * improving. The kinds of list operations inherited from 1252 * AbstractList are already so slow on COW sublists that 1253 * adding a bit more space/time doesn't seem even noticeable. 1254 */ 1255 private static class COWSubList<E> 1256 extends AbstractList<E> 1257 implements RandomAccess 1258 { 1259 private final CopyOnWriteArrayList<E> l; 1260 private final int offset; 1261 private int size; 1262 private Object[] expectedArray; 1263 1264 // only call this holding l's lock 1265 COWSubList(CopyOnWriteArrayList<E> list, 1266 int fromIndex, int toIndex) { 1267 l = list; 1268 expectedArray = l.getArray(); 1269 offset = fromIndex; 1270 size = toIndex - fromIndex; 1271 } 1272 1273 // only call this holding l's lock 1274 private void checkForComodification() { 1275 if (l.getArray() != expectedArray) 1276 throw new ConcurrentModificationException(); 1277 } 1278 1279 // only call this holding l's lock 1280 private void rangeCheck(int index) { 1281 if (index < 0 || index >= size) 1282 throw new IndexOutOfBoundsException("Index: "+index+ 1283 ",Size: "+size); 1284 } 1285 1286 public E set(int index, E element) { 1287 final ReentrantLock lock = l.lock; 1288 lock.lock(); 1289 try { 1290 rangeCheck(index); 1291 checkForComodification(); 1292 E x = l.set(index+offset, element); 1293 expectedArray = l.getArray(); 1294 return x; 1295 } finally { 1296 lock.unlock(); 1297 } 1298 } 1299 1300 public E get(int index) { 1301 final ReentrantLock lock = l.lock; 1302 lock.lock(); 1303 try { 1304 rangeCheck(index); 1305 checkForComodification(); 1306 return l.get(index+offset); 1307 } finally { 1308 lock.unlock(); 1309 } 1310 } 1311 1312 public int size() { 1313 final ReentrantLock lock = l.lock; 1314 lock.lock(); 1315 try { 1316 checkForComodification(); 1317 return size; 1318 } finally { 1319 lock.unlock(); 1320 } 1321 } 1322 1323 public void add(int index, E element) { 1324 final ReentrantLock lock = l.lock; 1325 lock.lock(); 1326 try { 1327 checkForComodification(); 1328 if (index < 0 || index > size) 1329 throw new IndexOutOfBoundsException(); 1330 l.add(index+offset, element); 1331 expectedArray = l.getArray(); 1332 size++; 1333 } finally { 1334 lock.unlock(); 1335 } 1336 } 1337 1338 public void clear() { 1339 final ReentrantLock lock = l.lock; 1340 lock.lock(); 1341 try { 1342 checkForComodification(); 1343 l.removeRange(offset, offset+size); 1344 expectedArray = l.getArray(); 1345 size = 0; 1346 } finally { 1347 lock.unlock(); 1348 } 1349 } 1350 1351 public E remove(int index) { 1352 final ReentrantLock lock = l.lock; 1353 lock.lock(); 1354 try { 1355 rangeCheck(index); 1356 checkForComodification(); 1357 E result = l.remove(index+offset); 1358 expectedArray = l.getArray(); 1359 size--; 1360 return result; 1361 } finally { 1362 lock.unlock(); 1363 } 1364 } 1365 1366 public boolean remove(Object o) { 1367 int index = indexOf(o); 1368 if (index == -1) 1369 return false; 1370 remove(index); 1371 return true; 1372 } 1373 1374 public Iterator<E> iterator() { 1375 final ReentrantLock lock = l.lock; 1376 lock.lock(); 1377 try { 1378 checkForComodification(); 1379 return new COWSubListIterator<E>(l, 0, offset, size); 1380 } finally { 1381 lock.unlock(); 1382 } 1383 } 1384 1385 public ListIterator<E> listIterator(int index) { 1386 final ReentrantLock lock = l.lock; 1387 lock.lock(); 1388 try { 1389 checkForComodification(); 1390 if (index < 0 || index > size) 1391 throw new IndexOutOfBoundsException("Index: "+index+ 1392 ", Size: "+size); 1393 return new COWSubListIterator<E>(l, index, offset, size); 1394 } finally { 1395 lock.unlock(); 1396 } 1397 } 1398 1399 public List<E> subList(int fromIndex, int toIndex) { 1400 final ReentrantLock lock = l.lock; 1401 lock.lock(); 1402 try { 1403 checkForComodification(); 1404 if (fromIndex < 0 || toIndex > size || fromIndex > toIndex) 1405 throw new IndexOutOfBoundsException(); 1406 return new COWSubList<E>(l, fromIndex + offset, 1407 toIndex + offset); 1408 } finally { 1409 lock.unlock(); 1410 } 1411 } 1412 1413 public void forEach(Consumer<? super E> action) { 1414 if (action == null) throw new NullPointerException(); 1415 int lo = offset; 1416 int hi = offset + size; 1417 Object[] a = expectedArray; 1418 if (l.getArray() != a) 1419 throw new ConcurrentModificationException(); 1420 if (lo < 0 || hi > a.length) 1421 throw new IndexOutOfBoundsException(); 1422 for (int i = lo; i < hi; ++i) { 1423 @SuppressWarnings("unchecked") E e = (E) a[i]; 1424 action.accept(e); 1425 } 1426 } 1427 1428 public void replaceAll(UnaryOperator<E> operator) { 1429 if (operator == null) throw new NullPointerException(); 1430 final ReentrantLock lock = l.lock; 1431 lock.lock(); 1432 try { 1433 int lo = offset; 1434 int hi = offset + size; 1435 Object[] elements = expectedArray; 1436 if (l.getArray() != elements) 1437 throw new ConcurrentModificationException(); 1438 int len = elements.length; 1439 if (lo < 0 || hi > len) 1440 throw new IndexOutOfBoundsException(); 1441 Object[] newElements = Arrays.copyOf(elements, len); 1442 for (int i = lo; i < hi; ++i) { 1443 @SuppressWarnings("unchecked") E e = (E) elements[i]; 1444 newElements[i] = operator.apply(e); 1445 } 1446 l.setArray(expectedArray = newElements); 1447 } finally { 1448 lock.unlock(); 1449 } 1450 } 1451 1452 public void sort(Comparator<? super E> c) { 1453 final ReentrantLock lock = l.lock; 1454 lock.lock(); 1455 try { 1456 int lo = offset; 1457 int hi = offset + size; 1458 Object[] elements = expectedArray; 1459 if (l.getArray() != elements) 1460 throw new ConcurrentModificationException(); 1461 int len = elements.length; 1462 if (lo < 0 || hi > len) 1463 throw new IndexOutOfBoundsException(); 1464 Object[] newElements = Arrays.copyOf(elements, len); 1465 @SuppressWarnings("unchecked") E[] es = (E[])newElements; 1466 Arrays.sort(es, lo, hi, c); 1467 l.setArray(expectedArray = newElements); 1468 } finally { 1469 lock.unlock(); 1470 } 1471 } 1472 1473 public boolean removeAll(Collection<?> c) { 1474 if (c == null) throw new NullPointerException(); 1475 boolean removed = false; 1476 final ReentrantLock lock = l.lock; 1477 lock.lock(); 1478 try { 1479 int n = size; 1480 if (n > 0) { 1481 int lo = offset; 1482 int hi = offset + n; 1483 Object[] elements = expectedArray; 1484 if (l.getArray() != elements) 1485 throw new ConcurrentModificationException(); 1486 int len = elements.length; 1487 if (lo < 0 || hi > len) 1488 throw new IndexOutOfBoundsException(); 1489 int newSize = 0; 1490 Object[] temp = new Object[n]; 1491 for (int i = lo; i < hi; ++i) { 1492 Object element = elements[i]; 1493 if (!c.contains(element)) 1494 temp[newSize++] = element; 1495 } 1496 if (newSize != n) { 1497 Object[] newElements = new Object[len - n + newSize]; 1498 System.arraycopy(elements, 0, newElements, 0, lo); 1499 System.arraycopy(temp, 0, newElements, lo, newSize); 1500 System.arraycopy(elements, hi, newElements, 1501 lo + newSize, len - hi); 1502 size = newSize; 1503 removed = true; 1504 l.setArray(expectedArray = newElements); 1505 } 1506 } 1507 } finally { 1508 lock.unlock(); 1509 } 1510 return removed; 1511 } 1512 1513 public boolean retainAll(Collection<?> c) { 1514 if (c == null) throw new NullPointerException(); 1515 boolean removed = false; 1516 final ReentrantLock lock = l.lock; 1517 lock.lock(); 1518 try { 1519 int n = size; 1520 if (n > 0) { 1521 int lo = offset; 1522 int hi = offset + n; 1523 Object[] elements = expectedArray; 1524 if (l.getArray() != elements) 1525 throw new ConcurrentModificationException(); 1526 int len = elements.length; 1527 if (lo < 0 || hi > len) 1528 throw new IndexOutOfBoundsException(); 1529 int newSize = 0; 1530 Object[] temp = new Object[n]; 1531 for (int i = lo; i < hi; ++i) { 1532 Object element = elements[i]; 1533 if (c.contains(element)) 1534 temp[newSize++] = element; 1535 } 1536 if (newSize != n) { 1537 Object[] newElements = new Object[len - n + newSize]; 1538 System.arraycopy(elements, 0, newElements, 0, lo); 1539 System.arraycopy(temp, 0, newElements, lo, newSize); 1540 System.arraycopy(elements, hi, newElements, 1541 lo + newSize, len - hi); 1542 size = newSize; 1543 removed = true; 1544 l.setArray(expectedArray = newElements); 1545 } 1546 } 1547 } finally { 1548 lock.unlock(); 1549 } 1550 return removed; 1551 } 1552 1553 public boolean removeIf(Predicate<? super E> filter) { 1554 if (filter == null) throw new NullPointerException(); 1555 boolean removed = false; 1556 final ReentrantLock lock = l.lock; 1557 lock.lock(); 1558 try { 1559 int n = size; 1560 if (n > 0) { 1561 int lo = offset; 1562 int hi = offset + n; 1563 Object[] elements = expectedArray; 1564 if (l.getArray() != elements) 1565 throw new ConcurrentModificationException(); 1566 int len = elements.length; 1567 if (lo < 0 || hi > len) 1568 throw new IndexOutOfBoundsException(); 1569 int newSize = 0; 1570 Object[] temp = new Object[n]; 1571 for (int i = lo; i < hi; ++i) { 1572 @SuppressWarnings("unchecked") E e = (E) elements[i]; 1573 if (!filter.test(e)) 1574 temp[newSize++] = e; 1575 } 1576 if (newSize != n) { 1577 Object[] newElements = new Object[len - n + newSize]; 1578 System.arraycopy(elements, 0, newElements, 0, lo); 1579 System.arraycopy(temp, 0, newElements, lo, newSize); 1580 System.arraycopy(elements, hi, newElements, 1581 lo + newSize, len - hi); 1582 size = newSize; 1583 removed = true; 1584 l.setArray(expectedArray = newElements); 1585 } 1586 } 1587 } finally { 1588 lock.unlock(); 1589 } 1590 return removed; 1591 } 1592 1593 public Spliterator<E> spliterator() { 1594 int lo = offset; 1595 int hi = offset + size; 1596 Object[] a = expectedArray; 1597 if (l.getArray() != a) 1598 throw new ConcurrentModificationException(); 1599 if (lo < 0 || hi > a.length) 1600 throw new IndexOutOfBoundsException(); 1601 return Spliterators.spliterator 1602 (a, lo, hi, Spliterator.IMMUTABLE | Spliterator.ORDERED); 1603 } 1604 1605 } 1606 1607 private static class COWSubListIterator<E> implements ListIterator<E> { 1608 private final ListIterator<E> it; 1609 private final int offset; 1610 private final int size; 1611 1612 COWSubListIterator(List<E> l, int index, int offset, int size) { 1613 this.offset = offset; 1614 this.size = size; 1615 it = l.listIterator(index+offset); 1616 } 1617 1618 public boolean hasNext() { 1619 return nextIndex() < size; 1620 } 1621 1622 public E next() { 1623 if (hasNext()) 1624 return it.next(); 1625 else 1626 throw new NoSuchElementException(); 1627 } 1628 1629 public boolean hasPrevious() { 1630 return previousIndex() >= 0; 1631 } 1632 1633 public E previous() { 1634 if (hasPrevious()) 1635 return it.previous(); 1636 else 1637 throw new NoSuchElementException(); 1638 } 1639 1640 public int nextIndex() { 1641 return it.nextIndex() - offset; 1642 } 1643 1644 public int previousIndex() { 1645 return it.previousIndex() - offset; 1646 } 1647 1648 public void remove() { 1649 throw new UnsupportedOperationException(); 1650 } 1651 1652 public void set(E e) { 1653 throw new UnsupportedOperationException(); 1654 } 1655 1656 public void add(E e) { 1657 throw new UnsupportedOperationException(); 1658 } 1659 1660 @Override 1661 public void forEachRemaining(Consumer<? super E> action) { 1662 Objects.requireNonNull(action); 1663 int s = size; 1664 ListIterator<E> i = it; 1665 while (nextIndex() < s) { 1666 action.accept(i.next()); 1667 } 1668 } 1669 } 1670 1671 // Support for resetting lock while deserializing 1672 private void resetLock() { 1673 UNSAFE.putObjectVolatile(this, lockOffset, new ReentrantLock()); 1674 } 1675 private static final sun.misc.Unsafe UNSAFE; 1676 private static final long lockOffset; 1677 static { 1678 try { 1679 UNSAFE = sun.misc.Unsafe.getUnsafe(); 1680 Class<?> k = CopyOnWriteArrayList.class; 1681 lockOffset = UNSAFE.objectFieldOffset 1682 (k.getDeclaredField("lock")); 1683 } catch (Exception e) { 1684 throw new Error(e); 1685 } 1686 } 1687 }