详解CopyOnWrite容器及其源码 (2)

add操作与set操作的大体过程都是相同的，多了两步的是，给新元素新增空间，即3~4步。
上面的add()方法是在容器最后添加一个元素，如果是在指定位置添加一个元素呢，源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
  public void add(int index, E element) {
final ReentrantLock lock = this.lock;
lock.lock(); // 1
try {
Object[] elements = getArray(); // 2
int len = elements.length; // 3
if (index > len || index < 0) // 4
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + len);
Object[] newElements;
int numMoved = len - index; // 5
if (numMoved == 0) // 6
newElements = Arrays.copyOf(elements, len + 1); // 7
else {
newElements = new Object[len + 1]; // 8
System.arraycopy(elements, 0, newElements, 0, index); // 9
System.arraycopy(elements, index, newElements, index + 1, numMoved); // 10
}
newElements[index] = element; // 11
setArray(newElements); // 12
} finally {
lock.unlock(); // 13
}
}
 

 

add(int index, E element)相比于add(E e)又多了数组元素移位的过程，即3~10步。移位的时候用到了System.arraycopy()方法，以第9步为例，其意为将elements数组从0开始的index个元素拷贝到newElements数组的从0开始的位置上。System.arraycopy()是一个native方法，用于保证每次add操作对数组移位时的性能不至于太差。
那么从容器中移除一个元素呢，请看其remove()方法源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
  public E remove(int index) {
final ReentrantLock lock = this.lock;
lock.lock(); // 1
try {
Object[] elements = getArray(); // 2
int len = elements.length; // 3
E oldValue = get(elements, index);
int numMoved = len - index - 1; // 4
if (numMoved == 0)
setArray(Arrays.copyOf(elements, len - 1)); // 5
else {
Object[] newElements = new Object[len - 1]; // 6
System.arraycopy(elements, 0, newElements, 0, index); //7
System.arraycopy(elements, index + 1, newElements, index, numMoved); // 8
setArray(newElements); // 9
}
return oldValue;
} finally {
lock.unlock(); // 10
}
}
 

 

remove(index)方法的实现与add(index, element) 方法的实现是类似的，区别在于前者是数组缩小。
除此之外，还提供了remove(Object o)方法用于移除特定值，remove(Object o, Object[] snapshot, int index)方法用于移除特定版本数组下的特定值，且前者的实现是以后者为基础的，故而前者在自己的实现中没有加锁。这里仅拿出第三个remove方法的源码来作分析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  private boolean remove(Object o, Object[] snapshot, int index) {
final ReentrantLock lock = this.lock;
lock.lock(); // 1
try {
Object[] current = getArray(); // 2
int len = current.length;
if (snapshot != current) findIndex: { // 3
int prefix = Math.min(index, len);
for (int i = 0; i < prefix; i++) {
if (current[i] != snapshot[i] && eq(o, current[i])) { // 4
index = i;
break findIndex;
}
}
if (index >= len) // 不存在要删除的元素
return false;
if (current[index] == o)
break findIndex;
index = indexOf(o, current, index, len); // 获取current数组中从index开始到len的值为o的第一个元素的位置
if (index < 0) // 不存在要删除的元素
return false;
}
Object[] newElements = new Object[len - 1]; // 5
System.arraycopy(current, 0, newElements, 0, index); // 6
System.arraycopy(current, index + 1, newElements, index, len - index - 1); // 7
setArray(newElements); // 8
return true;
} finally {
lock.unlock(); // 9
}
}