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