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