Java多线程系列--“JUC集合”02之 CopyOnWriteArrayList

时间:2022-01-20 18:00:36

出处:http://www.cnblogs.com/skywang12345/p/3498483.html

概要

本章是"JUC系列"的CopyOnWriteArrayList篇。接下来,会先对CopyOnWriteArrayList进行基本介绍,然后再说明它的原理,接着通过代码去分析,最后通过示例更进一步的了解CopyOnWriteArrayList。内容包括:
CopyOnWriteArrayList介绍
CopyOnWriteArrayList原理和数据结构

CopyOnWriteArrayList函数列表
CopyOnWriteArrayList源码分析(JDK1.7.0_40版本)
CopyOnWriteArrayList示例



CopyOnWriteArrayList介绍

它相当于线程安全的ArrayList。和ArrayList一样,它是个可变数组;但是和ArrayList不同的时,它具有以下特性:
1. 它最适合于具有以下特征的应用程序:List 大小通常保持很小,只读操作远多于可变操作,需要在遍历期间防止线程间的冲突。
2. 它是线程安全的。
3. 因为通常需要复制整个基础数组,所以可变操作(add()、set() 和 remove() 等等)的开销很大。
4. 迭代器支持hasNext(), next()等不可变操作,但不支持可变 remove()等操作。
5. 使用迭代器进行遍历的速度很快,并且不会与其他线程发生冲突。在构造迭代器时,迭代器依赖于不变的数组快照。

建议:在学习CopyOnWriteArraySet之前,先通过"Java 集合系列03之 ArrayList详细介绍(源码解析)和使用示例"对ArrayList进行了解!

 

CopyOnWriteArrayList原理和数据结构

CopyOnWriteArrayList的数据结构,如下图所示:

Java多线程系列--“JUC集合”02之 CopyOnWriteArrayList

说明
1. CopyOnWriteArrayList实现了List接口,因此它是一个队列。
2. CopyOnWriteArrayList包含了成员lock。每一个CopyOnWriteArrayList都和一个互斥锁lock绑定,通过lock,实现了对CopyOnWriteArrayList的互斥访问。
3. CopyOnWriteArrayList包含了成员array数组,这说明CopyOnWriteArrayList本质上通过数组实现的。

下面从“动态数组”和“线程安全”两个方面进一步对CopyOnWriteArrayList的原理进行说明。
1. CopyOnWriteArrayList的“动态数组”机制 --它内部有个“volatile数组”(array)来保持数据。在“添加/修改/删除”数据时,都会新建一个数组,并将更新后的数据拷贝到新建的数组中,最后再将该数组赋值给“volatile数组”。这就是它叫做CopyOnWriteArrayList的原因!CopyOnWriteArrayList就是通过这种方式实现的动态数组;不过正由于它在“添加/修改/删除”数据时,都会新建数组,所以涉及到修改数据的操作,CopyOnWriteArrayList效率很
低;但是单单只是进行遍历查找的话,效率比较高。
2. CopyOnWriteArrayList的“线程安全”机制 --是通过volatile和互斥锁来实现的。(01) CopyOnWriteArrayList是通过“volatile数组”来保存数据的。一个线程读取volatile数组时,总能看到其它线程对该volatile变量最后的写入;就这样,通过volatile提供了“读取到的数据总是最新的”这个机制的
保证。(02) CopyOnWriteArrayList通过互斥锁来保护数据。在“添加/修改/删除”数据时,会先“获取互斥锁”,再修改完毕之后,先将数据更新到“volatile数组”中,然后再“释放互斥锁”;这样,就达到了保护数据的目的。 

 

CopyOnWriteArrayList函数列表

Java多线程系列--“JUC集合”02之 CopyOnWriteArrayList
// 创建一个空列表。
CopyOnWriteArrayList()
// 创建一个按 collection 的迭代器返回元素的顺序包含指定 collection 元素的列表。
CopyOnWriteArrayList(Collection<? extends E> c)
// CopyOnWriteArrayList(E[] toCopyIn)
创建一个保存给定数组的副本的列表。

// 将指定元素添加到此列表的尾部。
boolean add(E e)
// 在此列表的指定位置上插入指定元素。
void add(int index, E element)
// 按照指定 collection 的迭代器返回元素的顺序,将指定 collection 中的所有元素添加此列表的尾部。
boolean addAll(Collection<? extends E> c)
// 从指定位置开始,将指定 collection 的所有元素插入此列表。
boolean addAll(int index, Collection<? extends E> c)
// 按照指定 collection 的迭代器返回元素的顺序,将指定 collection 中尚未包含在此列表中的所有元素添加列表的尾部。
int addAllAbsent(Collection<? extends E> c)
// 添加元素(如果不存在)。
boolean addIfAbsent(E e)
// 从此列表移除所有元素。
void clear()
// 返回此列表的浅表副本。
Object clone()
// 如果此列表包含指定的元素,则返回 true。
boolean contains(Object o)
// 如果此列表包含指定 collection 的所有元素,则返回 true。
boolean containsAll(Collection<?> c)
// 比较指定对象与此列表的相等性。
boolean equals(Object o)
// 返回列表中指定位置的元素。
E get(int index)
// 返回此列表的哈希码值。
int hashCode()
// 返回第一次出现的指定元素在此列表中的索引,从 index 开始向前搜索,如果没有找到该元素,则返回 -1。
int indexOf(E e, int index)
// 返回此列表中第一次出现的指定元素的索引;如果此列表不包含该元素,则返回 -1。
int indexOf(Object o)
// 如果此列表不包含任何元素,则返回 true。
boolean isEmpty()
// 返回以恰当顺序在此列表元素上进行迭代的迭代器。
Iterator<E> iterator()
// 返回最后一次出现的指定元素在此列表中的索引,从 index 开始向后搜索,如果没有找到该元素,则返回 -1。
int lastIndexOf(E e, int index)
// 返回此列表中最后出现的指定元素的索引;如果列表不包含此元素,则返回 -1。
int lastIndexOf(Object o)
// 返回此列表元素的列表迭代器(按适当顺序)。
ListIterator<E> listIterator()
// 返回列表中元素的列表迭代器(按适当顺序),从列表的指定位置开始。
ListIterator<E> listIterator(int index)
// 移除此列表指定位置上的元素。
E remove(int index)
// 从此列表移除第一次出现的指定元素(如果存在)。
boolean remove(Object o)
// 从此列表移除所有包含在指定 collection 中的元素。
boolean removeAll(Collection<?> c)
// 只保留此列表中包含在指定 collection 中的元素。
boolean retainAll(Collection<?> c)
// 用指定的元素替代此列表指定位置上的元素。
E set(int index, E element)
// 返回此列表中的元素数。
int size()
// 返回此列表中 fromIndex(包括)和 toIndex(不包括)之间部分的视图。
List<E> subList(int fromIndex, int toIndex)
// 返回一个按恰当顺序(从第一个元素到最后一个元素)包含此列表中所有元素的数组。
Object[] toArray()
// 返回以恰当顺序(从第一个元素到最后一个元素)包含列表所有元素的数组;返回数组的运行时类型是指定数组的运行时类型。
<T> T[] toArray(T[] a)
// 返回此列表的字符串表示形式。
String toString()
Java多线程系列--“JUC集合”02之 CopyOnWriteArrayList

 

CopyOnWriteArrayList源码分析(JDK1.7.0_40版本)

JDK1.7.0_40版本中CopyOnWriteArrayList.java的完整源码如下:

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

 

下面我们从“创建添加删除获取遍历”这5个方面去分析CopyOnWriteArrayList的原理。

1. 创建

CopyOnWriteArrayList共3个构造函数。它们的源码如下:

Java多线程系列--“JUC集合”02之 CopyOnWriteArrayList
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}

public CopyOnWriteArrayList(Collection<? extends E> c) {
Object[] elements = c.toArray();
if (elements.getClass() != Object[].class)
elements = Arrays.copyOf(elements, elements.length, Object[].class);
setArray(elements);
}

public CopyOnWriteArrayList(E[] toCopyIn) {
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
Java多线程系列--“JUC集合”02之 CopyOnWriteArrayList

说明:这3个构造函数都调用了setArray(),setArray()的源码如下:

Java多线程系列--“JUC集合”02之 CopyOnWriteArrayList
private volatile transient Object[] array;

final Object[] getArray() {
return array;
}

final void setArray(Object[] a) {
array = a;
}
Java多线程系列--“JUC集合”02之 CopyOnWriteArrayList

说明:setArray()的作用是给array赋值;其中,array是volatile transient Object[]类型,即array是“volatile数组”。
关于volatile关键字,我们知道“volatile能让变量变得可见”,即对一个volatile变量的读,总是能看到(任意线程)对这个volatile变量最后的写入。正在由于这种特性,每次更新了“volatile数组”之后,其它线程都能看到对它所做的更新。
关于transient关键字,它是在序列化中才起作用,transient变量不会被自动序列化。transient不是本文关注的重点,了解即可。
关于transient的更多内容,请参考:http://www.cnblogs.com/skywang12345/p/io_06.html

 

2. 添加

以add(E e)为例,来对“CopyOnWriteArrayList的添加操作”进行说明。下面是add(E e)的代码:

Java多线程系列--“JUC集合”02之 CopyOnWriteArrayList
public boolean add(E e) {
final ReentrantLock lock = this.lock;
// 获取“锁”
lock.lock();
try {
// 获取原始”volatile数组“中的数据和数据长度。
Object[] elements = getArray();
int len = elements.length;
// 新建一个数组newElements,并将原始数据拷贝到newElements中;
// newElements数组的长度=“原始数组的长度”+1
Object[] newElements = Arrays.copyOf(elements, len + 1);
// 将“新增加的元素”保存到newElements中。
newElements[len] = e;
// 将newElements赋值给”volatile数组“。
setArray(newElements);
return true;
} finally {
// 释放“锁”
lock.unlock();
}
}
Java多线程系列--“JUC集合”02之 CopyOnWriteArrayList

说明:add(E e)的作用就是将数据e添加到”volatile数组“中。它的实现方式是,新建一个数组,接着将原始的”volatile数组“的数据拷贝到新数组中,然后将新增数据也添加到新数组中;最后,将新数组赋值给”volatile数组“。
在add(E e)中有两点需要关注。
        第一,在”添加操作“开始前,获取独占锁(lock),若此时有需要线程要获取锁,则必须等待;在操作完毕后,释放独占锁(lock),此时其它线程才能获取锁。通过独占锁,来防止多线程同时修改数据!lock的定义如下:

transient final ReentrantLock lock = new ReentrantLock();

关于ReentrantLock的更多内容,可以参考:Java多线程系列--“JUC锁”02之 互斥锁ReentrantLock
        第二,操作完毕时,会通过setArray()来更新”volatile数组“。而且,前面我们提过”即对一个volatile变量的读,总是能看到(任意线程)对这个volatile变量最后的写入“;这样,每次添加元素之后,其它线程都能看到新添加的元素。

 

3. 获取

以get(int index)为例,来对“CopyOnWriteArrayList的删除操作”进行说明。下面是get(int index)的代码:

Java多线程系列--“JUC集合”02之 CopyOnWriteArrayList
public E get(int index) {
return get(getArray(), index);
}

private E get(Object[] a, int index) {
return (E) a[index];
}
Java多线程系列--“JUC集合”02之 CopyOnWriteArrayList

说明:get(int index)的实现很简单,就是返回”volatile数组“中的第index个元素。

 

4. 删除

以remove(int index)为例,来对“CopyOnWriteArrayList的删除操作”进行说明。下面是remove(int index)的代码:

Java多线程系列--“JUC集合”02之 CopyOnWriteArrayList
public E remove(int index) {
final ReentrantLock lock = this.lock;
// 获取“锁”
lock.lock();
try {
// 获取原始”volatile数组“中的数据和数据长度。
Object[] elements = getArray();
int len = elements.length;
// 获取elements数组中的第index个数据。
E oldValue = get(elements, index);
int numMoved = len - index - 1;
// 如果被删除的是最后一个元素,则直接通过Arrays.copyOf()进行处理,而不需要新建数组。
// 否则,新建数组,然后将”volatile数组中被删除元素之外的其它元素“拷贝到新数组中;最后,将新数组赋值给”volatile数组“。
if (numMoved == 0)
setArray(Arrays.copyOf(elements, len - 1));
else {
Object[] newElements = new Object[len - 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
setArray(newElements);
}
return oldValue;
} finally {
// 释放“锁”
lock.unlock();
}
}
Java多线程系列--“JUC集合”02之 CopyOnWriteArrayList

说明:remove(int index)的作用就是将”volatile数组“中第index个元素删除。它的实现方式是,如果被删除的是最后一个元素,则直接通过Arrays.copyOf()进行处理,而不需要新建数组。否则,新建数组,然后将”volatile数组中被删除元素之外的其它元素“拷贝到新数组中;最后,将新数组赋值给”volatile数组“。
         和add(E e)一样,remove(int index)也是”在操作之前,获取独占锁;操作完成之后,释放独占是“;并且”在操作完成时,会通过将数据更新到volatile数组中“。

 

5. 遍历

以iterator()为例,来对“CopyOnWriteArrayList的遍历操作”进行说明。下面是iterator()的代码:

public Iterator<E> iterator() {
return new COWIterator<E>(getArray(), 0);
}

说明:iterator()会返回COWIterator对象。

COWIterator实现额ListIterator接口,它的源码如下:

Java多线程系列--“JUC集合”02之 CopyOnWriteArrayList
private static class COWIterator<E> implements ListIterator<E> {
private final Object[] snapshot;
private int cursor;

private COWIterator(Object[] elements, int initialCursor) {
cursor = initialCursor;
snapshot = elements;
}

public boolean hasNext() {
return cursor < snapshot.length;
}

public boolean hasPrevious() {
return cursor > 0;
}

// 获取下一个元素
@SuppressWarnings("unchecked")
public E next() {
if (! hasNext())
throw new NoSuchElementException();
return (E) snapshot[cursor++];
}

// 获取上一个元素
@SuppressWarnings("unchecked")
public E previous() {
if (! hasPrevious())
throw new NoSuchElementException();
return (E) snapshot[--cursor];
}

public int nextIndex() {
return cursor;
}

public int previousIndex() {
return cursor-1;
}

public void remove() {
throw new UnsupportedOperationException();
}

public void set(E e) {
throw new UnsupportedOperationException();
}

public void add(E e) {
throw new UnsupportedOperationException();
}
}
Java多线程系列--“JUC集合”02之 CopyOnWriteArrayList

说明:COWIterator不支持修改元素的操作。例如,对于remove(),set(),add()等操作,COWIterator都会抛出异常!
另外,需要提到的一点是,CopyOnWriteArrayList返回迭代器不会抛出ConcurrentModificationException异常,即它不是fail-fast机制的!