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