CopyOnWriteArrayList.java revision aeeaa64fb691606d39bd24305001a4f4c71acdc3
1/* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with this 4 * work for additional information regarding copyright ownership. The ASF 5 * licenses this file to you under the Apache License, Version 2.0 (the 6 * "License"); you may not use this file except in compliance with the License. 7 * You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 13 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 14 * License for the specific language governing permissions and limitations under 15 * the License. 16 */ 17 18package java.util.concurrent; 19 20import java.io.IOException; 21import java.io.ObjectInputStream; 22import java.io.ObjectOutputStream; 23import java.io.Serializable; 24import java.lang.reflect.Array; 25import java.util.Collection; 26import java.util.ConcurrentModificationException; 27import java.util.Iterator; 28import java.util.List; 29import java.util.ListIterator; 30import java.util.NoSuchElementException; 31import java.util.RandomAccess; 32import java.util.concurrent.locks.ReentrantLock; 33 34/** 35 * Implements a {@link java.util.ArrayList} variant that is thread-safe. All 36 * write operation result in a new copy of the underlying data being created. 37 * Iterators reflect the state of the CopyOnWriteArrayList at the time they were 38 * created. They are not updated to reflect subsequent changes to the list. In 39 * addition, these iterators cannot be used for modifying the underlying 40 * CopyOnWriteArrayList. 41 * 42 * @param <E> the element type 43 */ 44public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, Serializable { 45 46 private static final long serialVersionUID = 8673264195747942595L; 47 48 private transient volatile E[] arr; 49 50 /** 51 * Lock for the queue write methods 52 */ 53 private final transient ReentrantLock lock = new ReentrantLock(); 54 55 /** 56 * Creates a new, empty instance of CopyOnWriteArrayList. 57 */ 58 public CopyOnWriteArrayList() { 59 } 60 61 /** 62 * Creates a new instance of CopyOnWriteArrayList and fills it with the 63 * contents of a given Collection. 64 * 65 * @param c the collection the elements of which are to be copied into 66 * the new instance. 67 */ 68 public CopyOnWriteArrayList(Collection<? extends E> c) { 69 this((E[]) c.toArray()); 70 } 71 72 /** 73 * Creates a new instance of CopyOnWriteArrayList and fills it with the 74 * contents of a given array. 75 * 76 * @param array the array the elements of which are to be copied into the 77 * new instance. 78 */ 79 public CopyOnWriteArrayList(E[] array) { 80 int size = array.length; 81 E[] data = newElementArray(size); 82 for (int i = 0; i < size; i++) { 83 data[i] = array[i]; 84 } 85 arr = data; 86 } 87 88 public boolean add(E e) { 89 lock.lock(); 90 try { 91 E[] data; 92 E[] old = getData(); 93 int size = old.length; 94 data = newElementArray(size + 1); 95 System.arraycopy(old, 0, data, 0, size); 96 data[size] = e; 97 setData(data); 98 return true; 99 } finally { 100 lock.unlock(); 101 } 102 } 103 104 public void add(int index, E e) { 105 lock.lock(); 106 try { 107 E[] data; 108 E[] old = getData(); 109 int size = old.length; 110 checkIndexInclusive(index, size); 111 data = newElementArray(size+1); 112 System.arraycopy(old, 0, data, 0, index); 113 data[index] = e; 114 if (size > index) { 115 System.arraycopy(old, index, data, index + 1, size - index); 116 } 117 setData(data); 118 } finally { 119 lock.unlock(); 120 } 121 } 122 123 public boolean addAll(Collection<? extends E> c) { 124 Iterator it = c.iterator(); 125 int ssize = c.size(); 126 lock.lock(); 127 try { 128 int size = size(); 129 E[] data; 130 E[] old = getData(); 131 int nSize = size + ssize; 132 data = newElementArray(nSize); 133 System.arraycopy(old, 0, data, 0, size); 134 while (it.hasNext()) { 135 data[size++] = (E) it.next(); 136 } 137 setData(data); 138 } finally { 139 lock.unlock(); 140 } 141 return true; 142 } 143 144 public boolean addAll(int index, Collection<? extends E> c) { 145 Iterator it = c.iterator(); 146 int ssize = c.size(); 147 lock.lock(); 148 try { 149 int size = size(); 150 checkIndexInclusive(index, size); 151 E[] data; 152 E[] old = getData(); 153 int nSize = size + ssize; 154 data = newElementArray(nSize); 155 System.arraycopy(old, 0, data, 0, index); 156 int i = index; 157 while (it.hasNext()) { 158 data[i++] = (E) it.next(); 159 } 160 if (size > index) { 161 System.arraycopy(old, index, data, index + ssize, size - index); 162 } 163 setData(data); 164 } finally { 165 lock.unlock(); 166 } 167 return true; 168 } 169 170 /** 171 * Adds to this CopyOnWriteArrayList all those elements from a given 172 * collection that are not yet part of the list. 173 * 174 * @param c the collection from which the potential new elements are 175 * taken. 176 * 177 * @return the number of elements actually added to this list. 178 */ 179 public int addAllAbsent(Collection<? extends E> c) { 180 if (c.size() == 0) { 181 return 0; 182 } 183 lock.lock(); 184 try { 185 E[] old = getData(); 186 int size = old.length; 187 E[] toAdd = newElementArray(c.size()); 188 int i = 0; 189 for (Iterator it = c.iterator(); it.hasNext();) { 190 E o = (E) it.next(); 191 if (indexOf(o) < 0) { 192 toAdd[i++] = o; 193 } 194 } 195 E[] data = newElementArray(size + i); 196 System.arraycopy(old, 0, data, 0, size); 197 System.arraycopy(toAdd, 0, data, size, i); 198 setData(data); 199 return i; 200 } finally { 201 lock.unlock(); 202 } 203 } 204 205 /** 206 * Adds to this CopyOnWriteArrayList another element, given that this 207 * element is not yet part of the list. 208 * 209 * @param e the potential new element. 210 * 211 * @return true if the element was added, or false otherwise. 212 */ 213 public boolean addIfAbsent(E e) { 214 lock.lock(); 215 try { 216 E[] data; 217 E[] old = getData(); 218 int size = old.length; 219 if (size != 0) { 220 if (indexOf(e) >= 0) { 221 return false; 222 } 223 } 224 data = newElementArray(size + 1); 225 System.arraycopy(old, 0, data, 0, size); 226 data[size] = e; 227 setData(data); 228 return true; 229 } finally { 230 lock.unlock(); 231 } 232 } 233 234 public void clear() { 235 lock.lock(); 236 try { 237 setData(newElementArray(0)); 238 } finally { 239 lock.unlock(); 240 } 241 } 242 243 @Override 244 public Object clone() { 245 try { 246 CopyOnWriteArrayList thisClone = (CopyOnWriteArrayList) super.clone(); 247 thisClone.setData(this.getData()); 248 return thisClone; 249 } catch (CloneNotSupportedException e) { 250 throw new RuntimeException("CloneNotSupportedException is not expected here"); 251 } 252 } 253 254 public boolean contains(Object o) { 255 return indexOf(o) >= 0; 256 } 257 258 public boolean containsAll(Collection<?> c) { 259 E[] data = getData(); 260 return containsAll(c, data, 0, data.length); 261 } 262 263 public boolean equals(Object o) { 264 if (o == this) { 265 return true; 266 } 267 if (!(o instanceof List)) { 268 return false; 269 } 270 List l = (List) o; 271 Iterator it = l.listIterator(); 272 Iterator ourIt = listIterator(); 273 while (it.hasNext()) { 274 if (!ourIt.hasNext()) { 275 return false; 276 } 277 Object thisListElem = it.next(); 278 Object anotherListElem = ourIt.next(); 279 if (!(thisListElem == null ? anotherListElem == null : thisListElem 280 .equals(anotherListElem))) { 281 return false; 282 } 283 } 284 if (ourIt.hasNext()) { 285 return false; 286 } 287 return true; 288 } 289 290 public E get(int index) { 291 E[] data = getData(); 292 return data[index]; 293 } 294 295 public int hashCode() { 296 int hashCode = 1; 297 Iterator it = listIterator(); 298 while (it.hasNext()) { 299 Object obj = it.next(); 300 hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode()); 301 } 302 return hashCode; 303 } 304 305 /** 306 * Returns the index of a given element, starting the search from a given 307 * position in the list. 308 * 309 * @param e the element to search. 310 * @param index the index at which to start the search. 311 * 312 * @return the index of the element or null, if the element has not been 313 * found at or beyond the given start index. 314 */ 315 public int indexOf(E e, int index) { 316 E[] data = getData(); 317 return indexOf(e, data, index, data.length - index); 318 } 319 320 public int indexOf(Object o) { 321 E[] data = getData(); 322 return indexOf(o, data, 0, data.length); 323 } 324 325 public boolean isEmpty() { 326 return size() == 0; 327 } 328 329 public Iterator<E> iterator() { 330 return new ListIteratorImpl(getData(), 0); 331 } 332 333 /** 334 * Returns the last index of a given element, starting the search from 335 * a given position in the list and going backwards. 336 * 337 * @param e the element to search. 338 * @param index the index at which to start the search. 339 * 340 * @return the index of the element or null, if the element has not been 341 * found at or before the given start index. 342 */ 343 public int lastIndexOf(E e, int index) { 344 E[] data = getData(); 345 return lastIndexOf(e, data, 0, index); 346 } 347 348 public int lastIndexOf(Object o) { 349 E[] data = getData(); 350 return lastIndexOf(o, data, 0, data.length); 351 } 352 353 public ListIterator<E> listIterator() { 354 return new ListIteratorImpl(getData(), 0); 355 } 356 357 public ListIterator<E> listIterator(int index) { 358 E[] data = getData(); 359 checkIndexInclusive(index, data.length); 360 return new ListIteratorImpl(data, index); 361 } 362 363 public E remove(int index) { 364 return removeRange(index, 1); 365 } 366 367 public boolean remove(Object o) { 368 lock.lock(); 369 try { 370 int index = indexOf(o); 371 if (index == -1) { 372 return false; 373 } 374 remove(index); 375 return true; 376 } finally { 377 lock.unlock(); 378 } 379 } 380 381 public boolean removeAll(Collection<?> c) { 382 lock.lock(); 383 try { 384 return removeAll(c, 0, getData().length) != 0; 385 } finally { 386 lock.unlock(); 387 } 388 } 389 390 public boolean retainAll(Collection<?> c) { 391 if (c == null) { 392 throw new NullPointerException(); 393 } 394 lock.lock(); 395 try { 396 return retainAll(c, 0, getData().length) != 0; 397 } finally { 398 lock.unlock(); 399 } 400 } 401 402 public E set(int index, E e) { 403 lock.lock(); 404 try { 405 int size = size(); 406 checkIndexExlusive(index, size); 407 E[] data; 408 data = newElementArray(size); 409 E[] oldArr = getData(); 410 System.arraycopy(oldArr, 0, data, 0, size); 411 E old = data[index]; 412 data[index] = e; 413 setData(data); 414 return old; 415 } finally { 416 lock.unlock(); 417 } 418 } 419 420 public int size() { 421 return getData().length; 422 } 423 424 public List<E> subList(int fromIndex, int toIndex) { 425 return new SubList(this, fromIndex, toIndex); 426 } 427 428 public Object[] toArray() { 429 E[] data = getData(); 430 return toArray(data, 0, data.length); 431 } 432 433 public <T> T[] toArray(T[] a) { 434 E[] data = getData(); 435 return (T[]) toArray(a, data, 0, data.length); 436 } 437 438 @Override 439 public String toString() { 440 StringBuilder sb = new StringBuilder("["); 441 442 Iterator it = listIterator(); 443 while (it.hasNext()) { 444 sb.append(String.valueOf(it.next())); 445 sb.append(", "); 446 } 447 if (sb.length() > 1) { 448 sb.setLength(sb.length() - 2); 449 } 450 sb.append("]"); 451 return sb.toString(); 452 } 453 454 // private and package private methods 455 456 @SuppressWarnings("unchecked") 457 private final E[] newElementArray(int size) { 458 return (E[])new Object[size]; 459 } 460 461 /** 462 * sets the internal data array 463 * 464 * @param data array to set 465 */ 466 private final void setData(E[] data) { 467 arr = data; 468 } 469 470 /** 471 * gets the internal data array (or a new array if it is null) 472 * 473 * @return the data array 474 */ 475 final E[] getData() { 476 if (arr == null) { 477 return newElementArray(0); 478 } 479 return arr; 480 } 481 482 /** 483 * Removes from the specified range of this list 484 * all the elements that are contained in the specified collection 485 * <p/> 486 * !should be called under lock 487 * 488 * @return Returns the number of removed elements 489 */ 490 final int removeAll(Collection c, int start, int size) { 491 int ssize = c.size(); 492 if (ssize == 0) { 493 return 0; 494 } 495 Object[] old = getData(); 496 int arrsize = old.length; 497 if (arrsize == 0) { 498 return 0; 499 } 500 Object[] data = new Object[size]; 501 int j = 0; 502 for (int i = start; i < (start + size); i++) { 503 if (!c.contains(old[i])) { 504 data[j++] = old[i]; 505 } 506 } 507 if (j != size) { 508 E[] result = newElementArray(arrsize - (size - j)); 509 System.arraycopy(old, 0, result, 0, start); 510 System.arraycopy(data, 0, result, start, j); 511 System.arraycopy(old, start + size, result, start + j, arrsize 512 - (start + size)); 513 setData(result); 514 return (size - j); 515 } 516 return 0; 517 } 518 519 /** 520 * Retains only the elements in the specified range of this list 521 * that are contained in the specified collection 522 * 523 * @return Returns the number of removed elements 524 */ 525 // should be called under lock 526 int retainAll(Collection c, int start, int size) { 527 Object[] old = getData(); 528 if (size == 0) { 529 return 0; 530 } 531 if (c.size() == 0) { 532 E[] data; 533 if (size == old.length) { 534 data = newElementArray(0); 535 } else { 536 data = newElementArray(old.length - size); 537 System.arraycopy(old, 0, data, 0, start); 538 System.arraycopy(old, start + size, data, start, old.length 539 - start - size); 540 } 541 setData(data); 542 return size; 543 } 544 Object[] temp = new Object[size]; 545 int pos = 0; 546 for (int i = start; i < (start + size); i++) { 547 if (c.contains(old[i])) { 548 temp[pos++] = old[i]; 549 } 550 } 551 if (pos == size) { 552 return 0; 553 } 554 E[] data = newElementArray(pos + old.length - size); 555 System.arraycopy(old, 0, data, 0, start); 556 System.arraycopy(temp, 0, data, start, pos); 557 System.arraycopy(old, start + size, data, start + pos, old.length 558 - start - size); 559 setData(data); 560 return (size - pos); 561 } 562 563 /** 564 * Removes specified range from this list 565 */ 566 E removeRange(int start, int size) { 567 lock.lock(); 568 try { 569 int sizeArr = size(); 570 checkIndexExlusive(start, sizeArr); 571 checkIndexInclusive(start + size, sizeArr); 572 E[] data; 573 data = newElementArray(sizeArr - size); 574 E[] oldArr = getData(); 575 System.arraycopy(oldArr, 0, data, 0, start); 576 E old = oldArr[start]; 577 if (sizeArr > (start + size)) { 578 System.arraycopy(oldArr, start + size, data, start, sizeArr 579 - (start + size)); 580 } 581 setData(data); 582 return old; 583 } finally { 584 lock.unlock(); 585 } 586 } 587 588 // some util static functions to use by iterators and methods 589 /** 590 * Returns an array containing all of the elements 591 * in the specified range of the array in proper sequence 592 */ 593 static Object[] toArray(Object[] data, int start, int size) { 594 Object[] result = new Object[size]; 595 System.arraycopy(data, start, result, 0, size); 596 return result; 597 } 598 599 /** 600 * Returns an array containing all of the elements 601 * in the specified range of the array in proper sequence, 602 * stores the result in the array, specified by first parameter 603 * (as for public instance method toArray(Object[] to) 604 */ 605 static Object[] toArray(Object[] to, Object[] data, int start, int size) { 606 int l = data.length; 607 if (to.length < l) { 608 to = (Object[]) Array.newInstance(to.getClass().getComponentType(), 609 l); 610 } else { 611 if (to.length > l) { 612 to[l] = null; 613 } 614 } 615 System.arraycopy(data, start, to, 0, size); 616 return to; 617 } 618 619 /** 620 * Checks if the specified range of the 621 * array contains all of the elements in the collection 622 * 623 * @param c collection with elements 624 * @param data array where to search the elements 625 * @param start start index 626 * @param size size of the range 627 */ 628 static final boolean containsAll(Collection c, Object[] data, int start, 629 int size) { 630 if (size == 0) { 631 return false; 632 } 633 Iterator it = c.iterator(); 634 while (it.hasNext()) { 635 Object next = it.next(); 636 if (indexOf(next, data, start, size) < 0) { 637 return false; 638 } 639 } 640 return true; 641 } 642 643 /** 644 * Returns the index in the specified range of the data array 645 * of the last occurrence of the specified element 646 * 647 * @param o element to search 648 * @param data array where to search 649 * @param start start index 650 * @param size size of the range 651 * @return 652 */ 653 static final int lastIndexOf(Object o, Object[] data, int start, int size) { 654 if (size == 0) { 655 return -1; 656 } 657 if (o != null) { 658 for (int i = start + size - 1; i > start - 1; i--) { 659 if (o.equals(data[i])) { 660 return i; 661 } 662 } 663 } else { 664 for (int i = start + size - 1; i > start - 1; i--) { 665 if (data[i] == null) { 666 return i; 667 } 668 } 669 } 670 return -1; 671 } 672 673 /** 674 * Returns the index in the specified range of the data array 675 * of the first occurrence of the specified element 676 * 677 * @param o element to search 678 * @param data array where to search 679 * @param start start index 680 * @param size end index 681 * @return 682 */ 683 static final int indexOf(Object o, Object[] data, int start, int size) { 684 if (size == 0) { 685 return -1; 686 } 687 if (o == null) { 688 for (int i = start; i < start + size; i++) { 689 if (data[i] == null) { 690 return i; 691 } 692 } 693 } else { 694 for (int i = start; i < start + size; i++) { 695 if (o.equals(data[i])) { 696 return i; 697 } 698 } 699 } 700 return -1; 701 } 702 703 /** 704 * Throws <code>IndexOutOfBoundsException</code> if <code>index</code> 705 * is out of the list bounds. 706 * 707 * @param index element index to check. 708 */ 709 static final void checkIndexInclusive(int index, int size) { 710 if (index < 0 || index > size) { 711 throw new IndexOutOfBoundsException("Index is " + index + ", size is " + size); 712 } 713 } 714 715 /** 716 * Throws <code>IndexOutOfBoundsException</code> if <code>index</code> 717 * is out of the list bounds. Excluding the last element. 718 * 719 * @param index element index to check. 720 */ 721 static final void checkIndexExlusive(int index, int size) { 722 if (index < 0 || index >= size) { 723 throw new IndexOutOfBoundsException("Index is " + index + ", size is " + size); 724 } 725 } 726 727 /** 728 * gets the internal data array 729 * 730 * @return the data array 731 */ 732 final E[] getArray() { 733 return arr; 734 } 735 736 /** 737 * list iterator implementation, 738 * when created gets snapshot of the list, 739 * so never throws ConcurrentModificationException 740 */ 741 private static class ListIteratorImpl implements ListIterator { 742 private final Object[] arr; 743 744 private int current; 745 746 private final int size; 747 748 final int size() { 749 return size; 750 } 751 752 public ListIteratorImpl(Object[] data, int current) { 753 this.current = current; 754 arr = data; 755 size = data.length; 756 } 757 758 public void add(Object o) { 759 throw new UnsupportedOperationException("Unsupported operation add"); 760 } 761 762 public boolean hasNext() { 763 if (current < size) { 764 return true; 765 } 766 return false; 767 } 768 769 public boolean hasPrevious() { 770 return current > 0; 771 } 772 773 public Object next() { 774 if (hasNext()) { 775 return arr[current++]; 776 } 777 throw new NoSuchElementException("pos is " + current + ", size is " + size); 778 } 779 780 public int nextIndex() { 781 return current; 782 } 783 784 public Object previous() { 785 if (hasPrevious()) { 786 return arr[--current]; 787 } 788 throw new NoSuchElementException("pos is " + (current-1) + ", size is " + size); 789 } 790 791 public int previousIndex() { 792 return current - 1; 793 } 794 795 public void remove() { 796 throw new UnsupportedOperationException("Unsupported operation remove"); 797 } 798 799 public void set(Object o) { 800 throw new UnsupportedOperationException("Unsupported operation set"); 801 } 802 803 } 804 805 /** 806 * Keeps a state of sublist implementation, 807 * size and array declared as final, 808 * so we'll never get the unconsistent state 809 */ 810 static final class SubListReadData { 811 final int size; 812 813 final Object[] data; 814 815 SubListReadData(int size, Object[] data) { 816 this.size = size; 817 this.data = data; 818 } 819 } 820 821 /** 822 * Represents a list returned by <code>sublist()</code>. 823 */ 824 static class SubList implements List { 825 private final CopyOnWriteArrayList list; 826 827 private volatile SubListReadData read; 828 829 private final int start; 830 831 /** 832 * Sublist constructor. 833 * 834 * @param list backing list. 835 * @param fromIdx startingIndex, inclusive 836 * @param toIdx endIndex, exclusive 837 */ 838 public SubList(CopyOnWriteArrayList list, int fromIdx, int toIdx) { 839 this.list = list; 840 Object[] data = list.getData(); 841 int size = toIdx - fromIdx; 842 checkIndexExlusive(fromIdx, data.length); 843 checkIndexInclusive(toIdx, data.length); 844 read = new SubListReadData(size, list.getData()); 845 start = fromIdx; 846 } 847 848 /** 849 * throws ConcurrentModificationException when the list 850 * is structurally modified in the other way other than via this subList 851 * <p/> 852 * Should be called under lock! 853 */ 854 private void checkModifications() { 855 if (read.data != list.getData()) { 856 throw new ConcurrentModificationException(); 857 } 858 } 859 860 /** 861 * @see java.util.List#listIterator(int) 862 */ 863 public ListIterator listIterator(int startIdx) { 864 return new SubListIterator(startIdx, read); 865 } 866 867 /** 868 * @see java.util.List#set(int, java.lang.Object) 869 */ 870 public Object set(int index, Object obj) { 871 list.lock.lock(); 872 try { 873 checkIndexExlusive(index, read.size); 874 checkModifications(); 875 Object result = list.set(index + start, obj); 876 read = new SubListReadData(read.size, list.getData()); 877 return result; 878 } finally { 879 list.lock.unlock(); 880 } 881 } 882 883 /** 884 * @see java.util.List#get(int) 885 */ 886 public Object get(int index) { 887 SubListReadData data = read; 888 if (data.data != list.getData()) { 889 list.lock.lock(); 890 try { 891 data = read; 892 if (data.data != list.getData()) { 893 throw new ConcurrentModificationException(); 894 } 895 } finally { 896 list.lock.unlock(); 897 } 898 } 899 checkIndexExlusive(index, data.size); 900 return data.data[index + start]; 901 } 902 903 /** 904 * @see java.util.Collection#size() 905 */ 906 public int size() { 907 return read.size; 908 } 909 910 /** 911 * @see java.util.List#remove(int) 912 */ 913 public Object remove(int index) { 914 list.lock.lock(); 915 try { 916 checkIndexExlusive(index, read.size); 917 checkModifications(); 918 Object obj = list.remove(index + start); 919 read = new SubListReadData(read.size - 1, list.getData()); 920 return obj; 921 } finally { 922 list.lock.unlock(); 923 } 924 } 925 926 /** 927 * @see java.util.List#add(int, java.lang.Object) 928 */ 929 public void add(int index, Object object) { 930 list.lock.lock(); 931 try { 932 checkIndexInclusive(index, read.size); 933 checkModifications(); 934 list.add(index + start, object); 935 read = new SubListReadData(read.size + 1, list.getData()); 936 } finally { 937 list.lock.unlock(); 938 } 939 } 940 941 public boolean add(Object o) { 942 list.lock.lock(); 943 try { 944 checkModifications(); 945 list.add(start + read.size, o); 946 read = new SubListReadData(read.size + 1, list.getData()); 947 return true; 948 } finally { 949 list.lock.unlock(); 950 } 951 } 952 953 public boolean addAll(Collection c) { 954 list.lock.lock(); 955 try { 956 checkModifications(); 957 int d = list.size(); 958 list.addAll(start + read.size, c); 959 read = new SubListReadData(read.size + (list.size() - d), list 960 .getData()); 961 return true; 962 } finally { 963 list.lock.unlock(); 964 } 965 } 966 967 public void clear() { 968 list.lock.lock(); 969 try { 970 checkModifications(); 971 list.removeRange(start, read.size); 972 read = new SubListReadData(0, list.getData()); 973 } finally { 974 list.lock.unlock(); 975 } 976 } 977 978 public boolean contains(Object o) { 979 return indexOf(o) != -1; 980 } 981 982 public boolean containsAll(Collection c) { 983 SubListReadData b = read; 984 return CopyOnWriteArrayList.containsAll(c, b.data, start, b.size); 985 } 986 987 public int indexOf(Object o) { 988 SubListReadData b = read; 989 int ind = CopyOnWriteArrayList.indexOf(o, b.data, start, b.size) 990 - start; 991 return ind < 0 ? -1 : ind; 992 } 993 994 public boolean isEmpty() { 995 return read.size == 0; 996 } 997 998 public Iterator iterator() { 999 return new SubListIterator(0, read); 1000 } 1001 1002 public int lastIndexOf(Object o) { 1003 SubListReadData b = read; 1004 int ind = CopyOnWriteArrayList 1005 .lastIndexOf(o, b.data, start, b.size) 1006 - start; 1007 return ind < 0 ? -1 : ind; 1008 } 1009 1010 public ListIterator listIterator() { 1011 return new SubListIterator(0, read); 1012 } 1013 1014 public boolean remove(Object o) { 1015 list.lock.lock(); 1016 try { 1017 checkModifications(); 1018 int i = indexOf(o); 1019 if (i == -1) { 1020 return false; 1021 } 1022 boolean result = list.remove(i + start) != null; 1023 if (result) { 1024 read = new SubListReadData(read.size - 1, list.getData()); 1025 } 1026 return result; 1027 } finally { 1028 list.lock.unlock(); 1029 } 1030 } 1031 1032 public boolean removeAll(Collection c) { 1033 list.lock.lock(); 1034 try { 1035 checkModifications(); 1036 int removed = list.removeAll(c, start, read.size); 1037 if (removed > 0) { 1038 read = new SubListReadData(read.size - removed, list 1039 .getData()); 1040 return true; 1041 } 1042 } finally { 1043 list.lock.unlock(); 1044 } 1045 return false; 1046 } 1047 1048 public boolean retainAll(Collection c) { 1049 list.lock.lock(); 1050 try { 1051 checkModifications(); 1052 int removed = list.retainAll(c, start, read.size); 1053 if (removed > 0) { 1054 read = new SubListReadData(read.size - removed, list 1055 .getData()); 1056 return true; 1057 } 1058 return false; 1059 } finally { 1060 list.lock.unlock(); 1061 } 1062 } 1063 1064 public List subList(int fromIndex, int toIndex) { 1065 return new SubList(list, start + fromIndex, start + toIndex); 1066 } 1067 1068 public Object[] toArray() { 1069 SubListReadData r = read; 1070 return CopyOnWriteArrayList.toArray(r.data, start, r.size); 1071 } 1072 1073 public Object[] toArray(Object[] a) { 1074 SubListReadData r = read; 1075 return CopyOnWriteArrayList.toArray(a, r.data, start, r.size); 1076 } 1077 1078 /** 1079 * @see java.util.List#addAll(int, java.util.Collection) 1080 */ 1081 public boolean addAll(int index, Collection collection) { 1082 list.lock.lock(); 1083 try { 1084 checkIndexInclusive(index, read.size); 1085 checkModifications(); 1086 int d = list.size(); 1087 boolean rt = list.addAll(index + start, collection); 1088 read = new SubListReadData(read.size + list.size() - d, list 1089 .getData()); 1090 return rt; 1091 } finally { 1092 list.lock.unlock(); 1093 } 1094 } 1095 1096 /** 1097 * Implementation of <code>ListIterator</code> for the 1098 * <code>SubList</code> 1099 * gets a snapshot of the sublist, 1100 * never throws ConcurrentModificationException 1101 */ 1102 private class SubListIterator extends ListIteratorImpl { 1103 private final SubListReadData dataR; 1104 1105 /** 1106 * Constructs an iterator starting with the given index 1107 * 1108 * @param index index of the first element to iterate. 1109 */ 1110 private SubListIterator(int index, SubListReadData d) { 1111 super(d.data, index + start); 1112 this.dataR = d; 1113 } 1114 1115 /** 1116 * @see java.util.ListIterator#nextIndex() 1117 */ 1118 public int nextIndex() { 1119 return super.nextIndex() - start; 1120 } 1121 1122 /** 1123 * @see java.util.ListIterator#previousIndex() 1124 */ 1125 public int previousIndex() { 1126 return super.previousIndex() - start; 1127 } 1128 1129 /** 1130 * @see java.util.Iterator#hasNext() 1131 */ 1132 public boolean hasNext() { 1133 return nextIndex() < dataR.size; 1134 } 1135 1136 /** 1137 * @see java.util.ListIterator#hasPrevious() 1138 */ 1139 public boolean hasPrevious() { 1140 return previousIndex() > -1; 1141 } 1142 } 1143 1144 } 1145 1146 //serialization support 1147 /** 1148 * Writes the object state to the ObjectOutputStream. 1149 * 1150 * @param oos ObjectOutputStream to write object to. 1151 * @throws IOException if an I/O error occur. 1152 */ 1153 private void writeObject(ObjectOutputStream oos) throws IOException { 1154 E[] back = getData(); 1155 int size = back.length; 1156 oos.defaultWriteObject(); 1157 oos.writeInt(size); 1158 for (int i = 0; i < size; i++) { 1159 oos.writeObject(back[i]); 1160 } 1161 } 1162 1163 /** 1164 * Reads the object state from the ObjectOutputStream. 1165 * 1166 * @param ois ObjectInputStream to read object from. 1167 * @throws IOException if an I/O error occur. 1168 */ 1169 private void readObject(ObjectInputStream ois) throws IOException, 1170 ClassNotFoundException { 1171 ois.defaultReadObject(); 1172 int length = ois.readInt(); 1173 if (length == 0) { 1174 setData(newElementArray(0)); 1175 } else { 1176 E[] back = newElementArray(length); 1177 for (int i = 0; i < back.length; i++) { 1178 back[i] = (E) ois.readObject(); 1179 } 1180 setData(back); 1181 } 1182 } 1183 1184} 1185