1. /*
  2. * @(#)CopyOnWriteArrayList.java 1.8 04/04/14
  3. *
  4. * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
  5. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
  6. */
  7. package java.util.concurrent;
  8. import java.util.*;
  9. /**
  10. * A thread-safe variant of {@link java.util.ArrayList} in which all mutative
  11. * operations (add, set, and so on) are implemented by making a fresh
  12. * copy of the underlying array.
  13. *
  14. * <p> This is ordinarily too costly, but may be <em>more</em> efficient
  15. * than alternatives when traversal operations vastly outnumber
  16. * mutations, and is useful when you cannot or don't want to
  17. * synchronize traversals, yet need to preclude interference among
  18. * concurrent threads. The "snapshot" style iterator method uses a
  19. * reference to the state of the array at the point that the iterator
  20. * was created. This array never changes during the lifetime of the
  21. * iterator, so interference is impossible and the iterator is
  22. * guaranteed not to throw <tt>ConcurrentModificationException</tt>.
  23. * The iterator will not reflect additions, removals, or changes to
  24. * the list since the iterator was created. Element-changing
  25. * operations on iterators themselves (remove, set, and add) are not
  26. * supported. These methods throw
  27. * <tt>UnsupportedOperationException</tt>.
  28. *
  29. * <p>This class is a member of the
  30. * <a href="{@docRoot}/../guide/collections/index.html">
  31. * Java Collections Framework</a>.
  32. *
  33. * @since 1.5
  34. * @author Doug Lea
  35. * @param <E> the type of elements held in this collection
  36. */
  37. public class CopyOnWriteArrayList<E>
  38. implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
  39. private static final long serialVersionUID = 8673264195747942595L;
  40. /**
  41. * The held array. Directly accessed only within synchronized
  42. * methods
  43. */
  44. private volatile transient E[] array;
  45. /**
  46. * Accessor to the array intended to be called from
  47. * within unsynchronized read-only methods
  48. **/
  49. private E[] array() { return array; }
  50. /**
  51. * Creates an empty list.
  52. */
  53. public CopyOnWriteArrayList() {
  54. array = (E[]) new Object[0];
  55. }
  56. /**
  57. * Creates a list containing the elements of the specified
  58. * Collection, in the order they are returned by the Collection's
  59. * iterator.
  60. * @param c the collection of initially held elements
  61. */
  62. public CopyOnWriteArrayList(Collection<? extends E> c) {
  63. array = (E[]) new Object[c.size()];
  64. Iterator<? extends E> i = c.iterator();
  65. int size = 0;
  66. while (i.hasNext())
  67. array[size++] = i.next();
  68. }
  69. /**
  70. * Create a new CopyOnWriteArrayList holding a copy of given array.
  71. *
  72. * @param toCopyIn the array (a copy of this array is used as the
  73. * internal array)
  74. **/
  75. public CopyOnWriteArrayList(E[] toCopyIn) {
  76. copyIn(toCopyIn, 0, toCopyIn.length);
  77. }
  78. /**
  79. * Replace the held array with a copy of the <tt>n</tt> elements
  80. * of the provided array, starting at position <tt>first</tt>. To
  81. * copy an entire array, call with arguments (array, 0,
  82. * array.length).
  83. * @param toCopyIn the array. A copy of the indicated elements of
  84. * this array is used as the internal array.
  85. * @param first The index of first position of the array to
  86. * start copying from.
  87. * @param n the number of elements to copy. This will be the new size of
  88. * the list.
  89. **/
  90. private synchronized void copyIn(E[] toCopyIn, int first, int n) {
  91. array = (E[]) new Object[n];
  92. System.arraycopy(toCopyIn, first, array, 0, n);
  93. }
  94. /**
  95. * Returns the number of elements in this list.
  96. *
  97. * @return the number of elements in this list.
  98. */
  99. public int size() {
  100. return array().length;
  101. }
  102. /**
  103. * Tests if this list has no elements.
  104. *
  105. * @return <tt>true</tt> if this list has no elements;
  106. * <tt>false</tt> otherwise.
  107. */
  108. public boolean isEmpty() {
  109. return size() == 0;
  110. }
  111. /**
  112. * Returns <tt>true</tt> if this list contains the specified element.
  113. *
  114. * @param elem element whose presence in this List is to be tested.
  115. * @return <code>true</code> if the specified element is present;
  116. * <code>false</code> otherwise.
  117. */
  118. public boolean contains(Object elem) {
  119. E[] elementData = array();
  120. int len = elementData.length;
  121. return indexOf(elem, elementData, len) >= 0;
  122. }
  123. /**
  124. * Searches for the first occurrence of the given argument, testing
  125. * for equality using the <tt>equals</tt> method.
  126. *
  127. * @param elem an object.
  128. * @return the index of the first occurrence of the argument in this
  129. * list; returns <tt>-1</tt> if the object is not found.
  130. * @see Object#equals(Object)
  131. */
  132. public int indexOf(Object elem) {
  133. E[] elementData = array();
  134. int len = elementData.length;
  135. return indexOf(elem, elementData, len);
  136. }
  137. /**
  138. * static version allows repeated call without needed
  139. * to grab lock for array each time
  140. **/
  141. private static int indexOf(Object elem, Object[] elementData, int len) {
  142. if (elem == null) {
  143. for (int i = 0; i < len; i++)
  144. if (elementData[i]==null)
  145. return i;
  146. } else {
  147. for (int i = 0; i < len; i++)
  148. if (elem.equals(elementData[i]))
  149. return i;
  150. }
  151. return -1;
  152. }
  153. /**
  154. * Searches for the first occurrence of the given argument, beginning
  155. * the search at <tt>index</tt>, and testing for equality using
  156. * the <tt>equals</tt> method.
  157. *
  158. * @param elem an object.
  159. * @param index the index to start searching from.
  160. * @return the index of the first occurrence of the object argument in
  161. * this List at position <tt>index</tt> or later in the
  162. * List; returns <tt>-1</tt> if the object is not found.
  163. * @see Object#equals(Object)
  164. */
  165. public int indexOf(E elem, int index) {
  166. E[] elementData = array();
  167. int elementCount = elementData.length;
  168. if (elem == null) {
  169. for (int i = index ; i < elementCount ; i++)
  170. if (elementData[i]==null)
  171. return i;
  172. } else {
  173. for (int i = index ; i < elementCount ; i++)
  174. if (elem.equals(elementData[i]))
  175. return i;
  176. }
  177. return -1;
  178. }
  179. /**
  180. * Returns the index of the last occurrence of the specified object in
  181. * this list.
  182. *
  183. * @param elem the desired element.
  184. * @return the index of the last occurrence of the specified object in
  185. * this list; returns -1 if the object is not found.
  186. */
  187. public int lastIndexOf(Object elem) {
  188. E[] elementData = array();
  189. int len = elementData.length;
  190. return lastIndexOf(elem, elementData, len);
  191. }
  192. private static int lastIndexOf(Object elem, Object[] elementData, int len) {
  193. if (elem == null) {
  194. for (int i = len-1; i >= 0; i--)
  195. if (elementData[i]==null)
  196. return i;
  197. } else {
  198. for (int i = len-1; i >= 0; i--)
  199. if (elem.equals(elementData[i]))
  200. return i;
  201. }
  202. return -1;
  203. }
  204. /**
  205. * Searches backwards for the specified object, starting from the
  206. * specified index, and returns an index to it.
  207. *
  208. * @param elem the desired element.
  209. * @param index the index to start searching from.
  210. * @return the index of the last occurrence of the specified object in this
  211. * List at position less than index in the List;
  212. * -1 if the object is not found.
  213. */
  214. public int lastIndexOf(E elem, int index) {
  215. // needed in order to compile on 1.2b3
  216. E[] elementData = array();
  217. if (elem == null) {
  218. for (int i = index; i >= 0; i--)
  219. if (elementData[i]==null)
  220. return i;
  221. } else {
  222. for (int i = index; i >= 0; i--)
  223. if (elem.equals(elementData[i]))
  224. return i;
  225. }
  226. return -1;
  227. }
  228. /**
  229. * Returns a shallow copy of this list. (The elements themselves
  230. * are not copied.)
  231. *
  232. * @return a clone of this list.
  233. */
  234. public Object clone() {
  235. try {
  236. E[] elementData = array();
  237. CopyOnWriteArrayList<E> v = (CopyOnWriteArrayList<E>)super.clone();
  238. v.array = (E[]) new Object[elementData.length];
  239. System.arraycopy(elementData, 0, v.array, 0, elementData.length);
  240. return v;
  241. } catch (CloneNotSupportedException e) {
  242. // this shouldn't happen, since we are Cloneable
  243. throw new InternalError();
  244. }
  245. }
  246. /**
  247. * Returns an array containing all of the elements in this list
  248. * in the correct order.
  249. * @return an array containing all of the elements in this list
  250. * in the correct order.
  251. */
  252. public Object[] toArray() {
  253. Object[] elementData = array();
  254. Object[] result = new Object[elementData.length];
  255. System.arraycopy(elementData, 0, result, 0, elementData.length);
  256. return result;
  257. }
  258. /**
  259. * Returns an array containing all of the elements in this list in the
  260. * correct order. The runtime type of the returned array is that of the
  261. * specified array. If the list fits in the specified array, it is
  262. * returned therein. Otherwise, a new array is allocated with the runtime
  263. * type of the specified array and the size of this list.
  264. * <p>
  265. * If the list fits in the specified array with room to spare
  266. * (i.e., the array has more elements than the list),
  267. * the element in the array immediately following the end of the
  268. * collection is set to null. This is useful in determining the length
  269. * of the list <em>only</em> if the caller knows that the list
  270. * does not contain any null elements.
  271. *
  272. * @param a the array into which the elements of the list are to
  273. * be stored, if it is big enough; otherwise, a new array of the
  274. * same runtime type is allocated for this purpose.
  275. * @return an array containing the elements of the list.
  276. * @throws ArrayStoreException the runtime type of a is not a supertype
  277. * of the runtime type of every element in this list.
  278. */
  279. public <T> T[] toArray(T a[]) {
  280. E[] elementData = array();
  281. if (a.length < elementData.length)
  282. a = (T[])
  283. java.lang.reflect.Array.newInstance(a.getClass().getComponentType(),
  284. elementData.length);
  285. System.arraycopy(elementData, 0, a, 0, elementData.length);
  286. if (a.length > elementData.length)
  287. a[elementData.length] = null;
  288. return a;
  289. }
  290. // Positional Access Operations
  291. /**
  292. * Returns the element at the specified position in this list.
  293. *
  294. * @param index index of element to return.
  295. * @return the element at the specified position in this list.
  296. * @throws IndexOutOfBoundsException if index is out of range <tt>(index
  297. * < 0 || index >= size())</tt>.
  298. */
  299. public E get(int index) {
  300. E[] elementData = array();
  301. rangeCheck(index, elementData.length);
  302. return elementData[index];
  303. }
  304. /**
  305. * Replaces the element at the specified position in this list with
  306. * the specified element.
  307. *
  308. * @param index index of element to replace.
  309. * @param element element to be stored at the specified position.
  310. * @return the element previously at the specified position.
  311. * @throws IndexOutOfBoundsException if index out of range
  312. * <tt>(index < 0 || index >= size())</tt>.
  313. */
  314. public synchronized E set(int index, E element) {
  315. int len = array.length;
  316. rangeCheck(index, len);
  317. E oldValue = array[index];
  318. boolean same = (oldValue == element ||
  319. (element != null && element.equals(oldValue)));
  320. if (!same) {
  321. E[] newArray = (E[]) new Object[len];
  322. System.arraycopy(array, 0, newArray, 0, len);
  323. newArray[index] = element;
  324. array = newArray;
  325. }
  326. return oldValue;
  327. }
  328. /**
  329. * Appends the specified element to the end of this list.
  330. *
  331. * @param element element to be appended to this list.
  332. * @return true (as per the general contract of Collection.add).
  333. */
  334. public synchronized boolean add(E element) {
  335. int len = array.length;
  336. E[] newArray = (E[]) new Object[len+1];
  337. System.arraycopy(array, 0, newArray, 0, len);
  338. newArray[len] = element;
  339. array = newArray;
  340. return true;
  341. }
  342. /**
  343. * Inserts the specified element at the specified position in this
  344. * list. Shifts the element currently at that position (if any) and
  345. * any subsequent elements to the right (adds one to their indices).
  346. *
  347. * @param index index at which the specified element is to be inserted.
  348. * @param element element to be inserted.
  349. * @throws IndexOutOfBoundsException if index is out of range
  350. * <tt>(index < 0 || index > size())</tt>.
  351. */
  352. public synchronized void add(int index, E element) {
  353. int len = array.length;
  354. if (index > len || index < 0)
  355. throw new IndexOutOfBoundsException("Index: "+index+", Size: "+len);
  356. E[] newArray = (E[]) new Object[len+1];
  357. System.arraycopy(array, 0, newArray, 0, index);
  358. newArray[index] = element;
  359. System.arraycopy(array, index, newArray, index+1, len - index);
  360. array = newArray;
  361. }
  362. /**
  363. * Removes the element at the specified position in this list.
  364. * Shifts any subsequent elements to the left (subtracts one from their
  365. * indices).
  366. *
  367. * @param index the index of the element to removed.
  368. * @return the element that was removed from the list.
  369. * @throws IndexOutOfBoundsException if index out of range <tt>(index
  370. * < 0 || index >= size())</tt>.
  371. */
  372. public synchronized E remove(int index) {
  373. int len = array.length;
  374. rangeCheck(index, len);
  375. E oldValue = array[index];
  376. E[] newArray = (E[]) new Object[len-1];
  377. System.arraycopy(array, 0, newArray, 0, index);
  378. int numMoved = len - index - 1;
  379. if (numMoved > 0)
  380. System.arraycopy(array, index+1, newArray, index, numMoved);
  381. array = newArray;
  382. return oldValue;
  383. }
  384. /**
  385. * Removes a single instance of the specified element from this
  386. * list, if it is present (optional operation). More formally,
  387. * removes an element <tt>e</tt> such that <tt>(o==null ? e==null :
  388. * o.equals(e))</tt>, if the list contains one or more such
  389. * elements. Returns <tt>true</tt> if the list contained the
  390. * specified element (or equivalently, if the list changed as a
  391. * result of the call).<p>
  392. *
  393. * @param o element to be removed from this list, if present.
  394. * @return <tt>true</tt> if the list contained the specified element.
  395. */
  396. public synchronized boolean remove(Object o) {
  397. int len = array.length;
  398. if (len == 0) return false;
  399. // Copy while searching for element to remove
  400. // This wins in the normal case of element being present
  401. int newlen = len-1;
  402. E[] newArray = (E[]) new Object[newlen];
  403. for (int i = 0; i < newlen; ++i) {
  404. if (o == array[i] ||
  405. (o != null && o.equals(array[i]))) {
  406. // found one; copy remaining and exit
  407. for (int k = i + 1; k < len; ++k) newArray[k-1] = array[k];
  408. array = newArray;
  409. return true;
  410. } else
  411. newArray[i] = array[i];
  412. }
  413. // special handling for last cell
  414. if (o == array[newlen] ||
  415. (o != null && o.equals(array[newlen]))) {
  416. array = newArray;
  417. return true;
  418. } else
  419. return false; // throw away copy
  420. }
  421. /**
  422. * Removes from this List all of the elements whose index is between
  423. * fromIndex, inclusive and toIndex, exclusive. Shifts any succeeding
  424. * elements to the left (reduces their index).
  425. * This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements.
  426. * (If <tt>toIndex==fromIndex</tt>, this operation has no effect.)
  427. *
  428. * @param fromIndex index of first element to be removed.
  429. * @param toIndex index after last element to be removed.
  430. * @throws IndexOutOfBoundsException fromIndex or toIndex out of
  431. * range (fromIndex < 0 || fromIndex >= size() || toIndex
  432. * > size() || toIndex < fromIndex).
  433. */
  434. private synchronized void removeRange(int fromIndex, int toIndex) {
  435. int len = array.length;
  436. if (fromIndex < 0 || fromIndex >= len ||
  437. toIndex > len || toIndex < fromIndex)
  438. throw new IndexOutOfBoundsException();
  439. int numMoved = len - toIndex;
  440. int newlen = len - (toIndex-fromIndex);
  441. E[] newArray = (E[]) new Object[newlen];
  442. System.arraycopy(array, 0, newArray, 0, fromIndex);
  443. System.arraycopy(array, toIndex, newArray, fromIndex, numMoved);
  444. array = newArray;
  445. }
  446. /**
  447. * Append the element if not present.
  448. * @param element element to be added to this Collection, if absent.
  449. * @return true if added
  450. **/
  451. public synchronized boolean addIfAbsent(E element) {
  452. // Copy while checking if already present.
  453. // This wins in the most common case where it is not present
  454. int len = array.length;
  455. E[] newArray = (E[]) new Object[len + 1];
  456. for (int i = 0; i < len; ++i) {
  457. if (element == array[i] ||
  458. (element != null && element.equals(array[i])))
  459. return false; // exit, throwing away copy
  460. else
  461. newArray[i] = array[i];
  462. }
  463. newArray[len] = element;
  464. array = newArray;
  465. return true;
  466. }
  467. /**
  468. * Returns true if this Collection contains all of the elements in the
  469. * specified Collection.
  470. * <p>
  471. * This implementation iterates over the specified Collection, checking
  472. * each element returned by the Iterator in turn to see if it's
  473. * contained in this Collection. If all elements are so contained
  474. * true is returned, otherwise false.
  475. * @param c the collection
  476. * @return true if all elements are contained
  477. */
  478. public boolean containsAll(Collection<?> c) {
  479. E[] elementData = array();
  480. int len = elementData.length;
  481. Iterator e = c.iterator();
  482. while (e.hasNext())
  483. if (indexOf(e.next(), elementData, len) < 0)
  484. return false;
  485. return true;
  486. }
  487. /**
  488. * Removes from this Collection all of its elements that are contained in
  489. * the specified Collection. This is a particularly expensive operation
  490. * in this class because of the need for an internal temporary array.
  491. * <p>
  492. *
  493. * @param c the collection
  494. * @return true if this Collection changed as a result of the call.
  495. */
  496. public synchronized boolean removeAll(Collection<?> c) {
  497. E[] elementData = array;
  498. int len = elementData.length;
  499. if (len == 0) return false;
  500. // temp array holds those elements we know we want to keep
  501. E[] temp = (E[]) new Object[len];
  502. int newlen = 0;
  503. for (int i = 0; i < len; ++i) {
  504. E element = elementData[i];
  505. if (!c.contains(element)) {
  506. temp[newlen++] = element;
  507. }
  508. }
  509. if (newlen == len) return false;
  510. // copy temp as new array
  511. E[] newArray = (E[]) new Object[newlen];
  512. System.arraycopy(temp, 0, newArray, 0, newlen);
  513. array = newArray;
  514. return true;
  515. }
  516. /**
  517. * Retains only the elements in this Collection that are contained in the
  518. * specified Collection (optional operation). In other words, removes from
  519. * this Collection all of its elements that are not contained in the
  520. * specified Collection.
  521. * @param c the collection
  522. * @return true if this Collection changed as a result of the call.
  523. */
  524. public synchronized boolean retainAll(Collection<?> c) {
  525. E[] elementData = array;
  526. int len = elementData.length;
  527. if (len == 0) return false;
  528. E[] temp = (E[]) new Object[len];
  529. int newlen = 0;
  530. for (int i = 0; i < len; ++i) {
  531. E element = elementData[i];
  532. if (c.contains(element)) {
  533. temp[newlen++] = element;
  534. }
  535. }
  536. if (newlen == len) return false;
  537. E[] newArray = (E[]) new Object[newlen];
  538. System.arraycopy(temp, 0, newArray, 0, newlen);
  539. array = newArray;
  540. return true;
  541. }
  542. /**
  543. * Appends all of the elements in the specified Collection that
  544. * are not already contained in this list, to the end of
  545. * this list, in the order that they are returned by the
  546. * specified Collection's Iterator.
  547. *
  548. * @param c elements to be added into this list.
  549. * @return the number of elements added
  550. */
  551. public synchronized int addAllAbsent(Collection<? extends E> c) {
  552. int numNew = c.size();
  553. if (numNew == 0) return 0;
  554. E[] elementData = array;
  555. int len = elementData.length;
  556. E[] temp = (E[]) new Object[numNew];
  557. int added = 0;
  558. Iterator<? extends E> e = c.iterator();
  559. while (e.hasNext()) {
  560. E element = e.next();
  561. if (indexOf(element, elementData, len) < 0) {
  562. if (indexOf(element, temp, added) < 0) {
  563. temp[added++] = element;
  564. }
  565. }
  566. }
  567. if (added == 0) return 0;
  568. E[] newArray = (E[]) new Object[len+added];
  569. System.arraycopy(elementData, 0, newArray, 0, len);
  570. System.arraycopy(temp, 0, newArray, len, added);
  571. array = newArray;
  572. return added;
  573. }
  574. /**
  575. * Removes all of the elements from this list.
  576. *
  577. */
  578. public synchronized void clear() {
  579. array = (E[]) new Object[0];
  580. }
  581. /**
  582. * Appends all of the elements in the specified Collection to the end of
  583. * this list, in the order that they are returned by the
  584. * specified Collection's Iterator.
  585. *
  586. * @param c elements to be inserted into this list.
  587. * @return true if any elements are added
  588. */
  589. public synchronized boolean addAll(Collection<? extends E> c) {
  590. int numNew = c.size();
  591. if (numNew == 0) return false;
  592. int len = array.length;
  593. E[] newArray = (E[]) new Object[len+numNew];
  594. System.arraycopy(array, 0, newArray, 0, len);
  595. Iterator<? extends E> e = c.iterator();
  596. for (int i=0; i<numNew; i++)
  597. newArray[len++] = e.next();
  598. array = newArray;
  599. return true;
  600. }
  601. /**
  602. * Inserts all of the elements in the specified Collection into this
  603. * list, starting at the specified position. Shifts the element
  604. * currently at that position (if any) and any subsequent elements to
  605. * the right (increases their indices). The new elements will appear
  606. * in the list in the order that they are returned by the
  607. * specified Collection's iterator.
  608. *
  609. * @param index index at which to insert first element
  610. * from the specified collection.
  611. * @param c elements to be inserted into this list.
  612. * @throws IndexOutOfBoundsException index out of range (index
  613. * < 0 || index > size()).
  614. * @return true if any elements are added
  615. */
  616. public synchronized boolean addAll(int index, Collection<? extends E> c) {
  617. int len = array.length;
  618. if (index > len || index < 0)
  619. throw new IndexOutOfBoundsException("Index: "+index+", Size: "+len);
  620. int numNew = c.size();
  621. if (numNew == 0) return false;
  622. E[] newArray = (E[]) new Object[len+numNew];
  623. System.arraycopy(array, 0, newArray, 0, len);
  624. int numMoved = len - index;
  625. if (numMoved > 0)
  626. System.arraycopy(array, index, newArray, index + numNew, numMoved);
  627. Iterator<? extends E> e = c.iterator();
  628. for (int i=0; i<numNew; i++)
  629. newArray[index++] = e.next();
  630. array = newArray;
  631. return true;
  632. }
  633. /**
  634. * Check if the given index is in range. If not, throw an appropriate
  635. * runtime exception.
  636. */
  637. private void rangeCheck(int index, int length) {
  638. if (index >= length || index < 0)
  639. throw new IndexOutOfBoundsException("Index: "+index+", Size: "+ length);
  640. }
  641. /**
  642. * Save the state of the list to a stream (i.e., serialize it).
  643. *
  644. * @serialData The length of the array backing the list is emitted
  645. * (int), followed by all of its elements (each an Object)
  646. * in the proper order.
  647. * @param s the stream
  648. */
  649. private void writeObject(java.io.ObjectOutputStream s)
  650. throws java.io.IOException{
  651. // Write out element count, and any hidden stuff
  652. s.defaultWriteObject();
  653. E[] elementData = array();
  654. // Write out array length
  655. s.writeInt(elementData.length);
  656. // Write out all elements in the proper order.
  657. for (int i=0; i<elementData.length; i++)
  658. s.writeObject(elementData[i]);
  659. }
  660. /**
  661. * Reconstitute the list from a stream (i.e., deserialize it).
  662. * @param s the stream
  663. */
  664. private void readObject(java.io.ObjectInputStream s)
  665. throws java.io.IOException, ClassNotFoundException {
  666. // Read in size, and any hidden stuff
  667. s.defaultReadObject();
  668. // Read in array length and allocate array
  669. int arrayLength = s.readInt();
  670. E[] elementData = (E[]) new Object[arrayLength];
  671. // Read in all elements in the proper order.
  672. for (int i=0; i<elementData.length; i++)
  673. elementData[i] = (E) s.readObject();
  674. array = elementData;
  675. }
  676. /**
  677. * Returns a string representation of this Collection, containing
  678. * the String representation of each element.
  679. */
  680. public String toString() {
  681. StringBuffer buf = new StringBuffer();
  682. Iterator e = iterator();
  683. buf.append("[");
  684. int maxIndex = size() - 1;
  685. for (int i = 0; i <= maxIndex; i++) {
  686. buf.append(String.valueOf(e.next()));
  687. if (i < maxIndex)
  688. buf.append(", ");
  689. }
  690. buf.append("]");
  691. return buf.toString();
  692. }
  693. /**
  694. * Compares the specified Object with this List for equality. Returns true
  695. * if and only if the specified Object is also a List, both Lists have the
  696. * same size, and all corresponding pairs of elements in the two Lists are
  697. * <em>equal</em>. (Two elements <tt>e1</tt> and <tt>e2</tt> are
  698. * <em>equal</em> if <tt>(e1==null ? e2==null : e1.equals(e2))</tt>.)
  699. * In other words, two Lists are defined to be equal if they contain the
  700. * same elements in the same order.
  701. * <p>
  702. * This implementation first checks if the specified object is this
  703. * List. If so, it returns true; if not, it checks if the specified
  704. * object is a List. If not, it returns false; if so, it iterates over
  705. * both lists, comparing corresponding pairs of elements. If any
  706. * comparison returns false, this method returns false. If either
  707. * Iterator runs out of elements before the other it returns false
  708. * (as the Lists are of unequal length); otherwise it returns true when
  709. * the iterations complete.
  710. *
  711. * @param o the Object to be compared for equality with this List.
  712. * @return true if the specified Object is equal to this List.
  713. */
  714. public boolean equals(Object o) {
  715. if (o == this)
  716. return true;
  717. if (!(o instanceof List))
  718. return false;
  719. List<E> l2 = (List<E>)(o);
  720. if (size() != l2.size())
  721. return false;
  722. ListIterator<E> e1 = listIterator();
  723. ListIterator<E> e2 = l2.listIterator();
  724. while(e1.hasNext()) {
  725. E o1 = e1.next();
  726. E o2 = e2.next();
  727. if (!(o1==null ? o2==null : o1.equals(o2)))
  728. return false;
  729. }
  730. return true;
  731. }
  732. /**
  733. * Returns the hash code value for this List.
  734. *
  735. * <p> This implementation uses the definition in {@link
  736. * List#hashCode}.
  737. * @return the hash code
  738. */
  739. public int hashCode() {
  740. int hashCode = 1;
  741. Iterator<E> i = iterator();
  742. while (i.hasNext()) {
  743. E obj = i.next();
  744. hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
  745. }
  746. return hashCode;
  747. }
  748. /**
  749. * Returns an Iterator over the elements contained in this collection.
  750. * The iterator provides a snapshot of the state of the list
  751. * when the iterator was constructed. No synchronization is
  752. * needed while traversing the iterator. The iterator does
  753. * <em>NOT</em> support the <tt>remove</tt> method.
  754. * @return the iterator
  755. */
  756. public Iterator<E> iterator() {
  757. return new COWIterator<E>(array(), 0);
  758. }
  759. /**
  760. * Returns an Iterator of the elements in this List (in proper sequence).
  761. * The iterator provides a snapshot of the state of the list
  762. * when the iterator was constructed. No synchronization is
  763. * needed while traversing the iterator. The iterator does
  764. * <em>NOT</em> support the <tt>remove</tt>, <tt>set</tt>,
  765. * or <tt>add</tt> methods.
  766. * @return the iterator
  767. *
  768. */
  769. public ListIterator<E> listIterator() {
  770. return new COWIterator<E>(array(), 0);
  771. }
  772. /**
  773. * Returns a ListIterator of the elements in this List (in proper
  774. * sequence), starting at the specified position in the List. The
  775. * specified index indicates the first element that would be returned by
  776. * an initial call to nextElement. An initial call to previousElement
  777. * would return the element with the specified index minus one.
  778. * The ListIterator returned by this implementation will throw
  779. * an UnsupportedOperationException in its remove, set and
  780. * add methods.
  781. *
  782. * @param index index of first element to be returned from the
  783. * ListIterator (by a call to getNext).
  784. * @return the iterator
  785. * @throws IndexOutOfBoundsException index is out of range
  786. * (index < 0 || index > size()).
  787. */
  788. public ListIterator<E> listIterator(final int index) {
  789. E[] elementData = array();
  790. int len = elementData.length;
  791. if (index<0 || index>len)
  792. throw new IndexOutOfBoundsException("Index: "+index);
  793. return new COWIterator<E>(array(), index);
  794. }
  795. private static class COWIterator<E> implements ListIterator<E> {
  796. /** Snapshot of the array **/
  797. private final E[] array;
  798. /**
  799. * Index of element to be returned by subsequent call to next.
  800. */
  801. private int cursor;
  802. private COWIterator(E[] elementArray, int initialCursor) {
  803. array = elementArray;
  804. cursor = initialCursor;
  805. }
  806. public boolean hasNext() {
  807. return cursor < array.length;
  808. }
  809. public boolean hasPrevious() {
  810. return cursor > 0;
  811. }
  812. public E next() {
  813. try {
  814. return array[cursor++];
  815. } catch (IndexOutOfBoundsException ex) {
  816. throw new NoSuchElementException();
  817. }
  818. }
  819. public E previous() {
  820. try {
  821. return array[--cursor];
  822. } catch(IndexOutOfBoundsException e) {
  823. throw new NoSuchElementException();
  824. }
  825. }
  826. public int nextIndex() {
  827. return cursor;
  828. }
  829. public int previousIndex() {
  830. return cursor-1;
  831. }
  832. /**
  833. * Not supported. Always throws UnsupportedOperationException.
  834. * @throws UnsupportedOperationException remove is not supported
  835. * by this Iterator.
  836. */
  837. public void remove() {
  838. throw new UnsupportedOperationException();
  839. }
  840. /**
  841. * Not supported. Always throws UnsupportedOperationException.
  842. * @throws UnsupportedOperationException set is not supported
  843. * by this Iterator.
  844. */
  845. public void set(E o) {
  846. throw new UnsupportedOperationException();
  847. }
  848. /**
  849. * Not supported. Always throws UnsupportedOperationException.
  850. * @throws UnsupportedOperationException add is not supported
  851. * by this Iterator.
  852. */
  853. public void add(E o) {
  854. throw new UnsupportedOperationException();
  855. }
  856. }
  857. /**
  858. * Returns a view of the portion of this List between fromIndex,
  859. * inclusive, and toIndex, exclusive. The returned List is backed by this
  860. * List, so changes in the returned List are reflected in this List, and
  861. * vice-versa. While mutative operations are supported, they are
  862. * probably not very useful for CopyOnWriteArrayLists.
  863. * <p>
  864. * The semantics of the List returned by this method become undefined if
  865. * the backing list (i.e., this List) is <i>structurally modified</i> in
  866. * any way other than via the returned List. (Structural modifications are
  867. * those that change the size of the List, or otherwise perturb it in such
  868. * a fashion that iterations in progress may yield incorrect results.)
  869. *
  870. * @param fromIndex low endpoint (inclusive) of the subList.
  871. * @param toIndex high endpoint (exclusive) of the subList.
  872. * @return a view of the specified range within this List.
  873. * @throws IndexOutOfBoundsException Illegal endpoint index value
  874. * (fromIndex < 0 || toIndex > size || fromIndex > toIndex).
  875. */
  876. public synchronized List<E> subList(int fromIndex, int toIndex) {
  877. // synchronized since sublist constructor depends on it.
  878. int len = array.length;
  879. if (fromIndex<0 || toIndex>len || fromIndex>toIndex)
  880. throw new IndexOutOfBoundsException();
  881. return new COWSubList<E>(this, fromIndex, toIndex);
  882. }
  883. private static class COWSubList<E> extends AbstractList<E> {
  884. /*
  885. This class extends AbstractList merely for convenience, to
  886. avoid having to define addAll, etc. This doesn't hurt, but
  887. is wasteful. This class does not need or use modCount
  888. mechanics in AbstractList, but does need to check for
  889. concurrent modification using similar mechanics. On each
  890. operation, the array that we expect the backing list to use
  891. is checked and updated. Since we do this for all of the
  892. base operations invoked by those defined in AbstractList,
  893. all is well. While inefficient, this is not worth
  894. improving. The kinds of list operations inherited from
  895. AbstractList are already so slow on COW sublists that
  896. adding a bit more space/time doesn't seem even noticeable.
  897. */
  898. private final CopyOnWriteArrayList<E> l;
  899. private final int offset;
  900. private int size;
  901. private E[] expectedArray;
  902. private COWSubList(CopyOnWriteArrayList<E> list,
  903. int fromIndex, int toIndex) {
  904. l = list;
  905. expectedArray = l.array();
  906. offset = fromIndex;
  907. size = toIndex - fromIndex;
  908. }
  909. // only call this holding l's lock
  910. private void checkForComodification() {
  911. if (l.array != expectedArray)
  912. throw new ConcurrentModificationException();
  913. }
  914. // only call this holding l's lock
  915. private void rangeCheck(int index) {
  916. if (index<0 || index>=size)
  917. throw new IndexOutOfBoundsException("Index: "+index+ ",Size: "+size);
  918. }
  919. public E set(int index, E element) {
  920. synchronized(l) {
  921. rangeCheck(index);
  922. checkForComodification();
  923. E x = l.set(index+offset, element);
  924. expectedArray = l.array;
  925. return x;
  926. }
  927. }
  928. public E get(int index) {
  929. synchronized(l) {
  930. rangeCheck(index);
  931. checkForComodification();
  932. return l.get(index+offset);
  933. }
  934. }
  935. public int size() {
  936. synchronized(l) {
  937. checkForComodification();
  938. return size;
  939. }
  940. }
  941. public void add(int index, E element) {
  942. synchronized(l) {
  943. checkForComodification();
  944. if (index<0 || index>size)
  945. throw new IndexOutOfBoundsException();
  946. l.add(index+offset, element);
  947. expectedArray = l.array;
  948. size++;
  949. }
  950. }
  951. public void clear() {
  952. synchronized(l) {
  953. checkForComodification();
  954. l.removeRange(offset, offset+size);
  955. expectedArray = l.array;
  956. size = 0;
  957. }
  958. }
  959. public E remove(int index) {
  960. synchronized(l) {
  961. rangeCheck(index);
  962. checkForComodification();
  963. E result = l.remove(index+offset);
  964. expectedArray = l.array;
  965. size--;
  966. return result;
  967. }
  968. }
  969. public Iterator<E> iterator() {
  970. synchronized(l) {
  971. checkForComodification();
  972. return new COWSubListIterator<E>(l, 0, offset, size);
  973. }
  974. }
  975. public ListIterator<E> listIterator(final int index) {
  976. synchronized(l) {
  977. checkForComodification();
  978. if (index<0 || index>size)
  979. throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
  980. return new COWSubListIterator<E>(l, index, offset, size);
  981. }
  982. }
  983. public List<E> subList(int fromIndex, int toIndex) {
  984. synchronized(l) {
  985. checkForComodification();
  986. if (fromIndex<0 || toIndex>size)
  987. throw new IndexOutOfBoundsException();
  988. return new COWSubList<E>(l, fromIndex+offset, toIndex+offset);
  989. }
  990. }
  991. }
  992. private static class COWSubListIterator<E> implements ListIterator<E> {
  993. private final ListIterator<E> i;
  994. private final int index;
  995. private final int offset;
  996. private final int size;
  997. private COWSubListIterator(List<E> l, int index, int offset, int size) {
  998. this.index = index;
  999. this.offset = offset;
  1000. this.size = size;
  1001. i = l.listIterator(index+offset);
  1002. }
  1003. public boolean hasNext() {
  1004. return nextIndex() < size;
  1005. }
  1006. public E next() {
  1007. if (hasNext())
  1008. return i.next();
  1009. else
  1010. throw new NoSuchElementException();
  1011. }
  1012. public boolean hasPrevious() {
  1013. return previousIndex() >= 0;
  1014. }
  1015. public E previous() {
  1016. if (hasPrevious())
  1017. return i.previous();
  1018. else
  1019. throw new NoSuchElementException();
  1020. }
  1021. public int nextIndex() {
  1022. return i.nextIndex() - offset;
  1023. }
  1024. public int previousIndex() {
  1025. return i.previousIndex() - offset;
  1026. }
  1027. public void remove() {
  1028. throw new UnsupportedOperationException();
  1029. }
  1030. public void set(E o) {
  1031. throw new UnsupportedOperationException();
  1032. }
  1033. public void add(E o) {
  1034. throw new UnsupportedOperationException();
  1035. }
  1036. }
  1037. }