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