1 /*
2  * Copyright (C) 2010 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package libcore.java.util.concurrent;
18 
19 import java.util.ArrayList;
20 import java.util.Arrays;
21 import java.util.ConcurrentModificationException;
22 import java.util.Iterator;
23 import java.util.List;
24 import java.util.ListIterator;
25 import java.util.NoSuchElementException;
26 import java.util.concurrent.CopyOnWriteArrayList;
27 import java.util.concurrent.CountDownLatch;
28 import java.util.concurrent.ExecutorService;
29 import java.util.concurrent.Executors;
30 import java.util.concurrent.Future;
31 import junit.framework.TestCase;
32 import libcore.java.util.ForEachRemainingTester;
33 import libcore.util.SerializationTester;
34 public final class CopyOnWriteArrayListTest extends TestCase {
35 
testIteratorAndNonStructuralChanges()36     public void testIteratorAndNonStructuralChanges() {
37         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
38         list.addAll(Arrays.asList("a", "b", "c", "d", "e"));
39         Iterator<String> abcde = list.iterator();
40         assertEquals("a", abcde.next());
41         list.set(1, "B");
42         assertEquals("b", abcde.next());
43         assertEquals("c", abcde.next());
44         assertEquals("d", abcde.next());
45         assertEquals("e", abcde.next());
46     }
47 
48     /**
49      * The sub list throws on non-structural changes, even though that disagrees
50      * with the subList() documentation which suggests that only size-changing
51      * operations will trigger ConcurrentModificationException.
52      */
testSubListAndNonStructuralChanges()53     public void testSubListAndNonStructuralChanges() {
54         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
55         list.addAll(Arrays.asList("a", "b", "c", "d", "e"));
56         List<String> bcd = list.subList(1, 4);
57         list.set(2, "C");
58         try {
59             bcd.get(1);
60             fail();
61         } catch (ConcurrentModificationException expected) {
62         }
63     }
64 
testSubListAndStructuralChanges()65     public void testSubListAndStructuralChanges() {
66         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
67         list.addAll(Arrays.asList("a", "b", "c", "d", "e"));
68         List<String> bcd = list.subList(1, 4);
69         list.clear();
70         try {
71             bcd.get(1);
72             fail();
73         } catch (ConcurrentModificationException expected) {
74         }
75     }
76 
testSubListAndSizePreservingStructuralChanges()77     public void testSubListAndSizePreservingStructuralChanges() {
78         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
79         list.addAll(Arrays.asList("a", "b", "c", "d", "e"));
80         List<String> bcd = list.subList(1, 4);
81         list.clear();
82         list.addAll(Arrays.asList("A", "B", "C", "D", "E"));
83         try {
84             bcd.get(1);
85             fail();
86         } catch (ConcurrentModificationException expected) {
87         }
88     }
89 
testRemoveAll()90     public void testRemoveAll() {
91         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
92         list.addAll(Arrays.asList("a", "b", "c", "d", "e"));
93 
94         list.removeAll(Arrays.asList());
95         assertEquals(Arrays.asList("a", "b", "c", "d", "e"), list);
96 
97         list.removeAll(Arrays.asList("e"));
98         assertEquals(Arrays.asList("a", "b", "c", "d"), list);
99 
100         list.removeAll(Arrays.asList("b", "c"));
101         assertEquals(Arrays.asList("a", "d"), list);
102     }
103 
testSubListClear()104     public void testSubListClear() {
105         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
106         list.addAll(Arrays.asList("a", "b", "c", "d", "e"));
107         List<String> bcd = list.subList(1, 4);
108         bcd.clear();
109         assertEquals(Arrays.asList("a", "e"), list);
110         bcd.addAll(Arrays.asList("B", "C", "D"));
111         assertEquals(Arrays.asList("a", "B", "C", "D", "e"), list);
112     }
113 
testSubListClearWhenEmpty()114     public void testSubListClearWhenEmpty() {
115         new CopyOnWriteArrayList<String>().subList(0, 0).clear(); // the RI fails here
116     }
117 
testSubListIteratorGetsSnapshot()118     public void testSubListIteratorGetsSnapshot() {
119         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
120         list.addAll(Arrays.asList("a", "b", "c", "d", "e"));
121         Iterator<String> bcd = list.subList(1, 4).iterator();
122         list.clear();
123         assertEquals("b", bcd.next());
124         assertEquals("c", bcd.next());
125         assertEquals("d", bcd.next());
126         assertFalse(bcd.hasNext());
127     }
128 
testSubListRemoveByValue()129     public void testSubListRemoveByValue() {
130         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
131         list.addAll(Arrays.asList("a", "b", "c", "d", "e"));
132         List<String> bcd = list.subList(1, 4);
133         bcd.remove("c"); // the RI fails here
134         assertEquals(Arrays.asList("b", "d"), bcd);
135         assertEquals(Arrays.asList("a", "b", "d", "e"), list);
136     }
137 
testSubListRemoveByIndex()138     public void testSubListRemoveByIndex() {
139         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
140         list.addAll(Arrays.asList("a", "b", "c", "d", "e"));
141         List<String> bcd = list.subList(1, 4);
142         bcd.remove(1);
143         assertEquals(Arrays.asList("b", "d"), bcd);
144         assertEquals(Arrays.asList("a", "b", "d", "e"), list);
145     }
146 
testSubListRetainAll()147     public void testSubListRetainAll() {
148         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
149         list.addAll(Arrays.asList("a", "b", "c", "d", "e", "f", "g", "h", "i"));
150         List<String> def = list.subList(3, 6);
151         def.retainAll(Arrays.asList("c", "e", "h")); // the RI fails here
152         assertEquals(Arrays.asList("a", "b", "c", "e", "g", "h", "i"), list);
153         assertEquals(Arrays.asList("e"), def);
154     }
155 
testSubListRemoveAll()156     public void testSubListRemoveAll() {
157         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
158         list.addAll(Arrays.asList("a", "b", "c", "d", "e", "f", "g", "h", "i"));
159         List<String> def = list.subList(3, 6);
160         def.removeAll(Arrays.asList("c", "e", "h"));  // the RI fails here
161         assertEquals(Arrays.asList("a", "b", "c", "d", "f", "g", "h", "i"), list);
162         assertEquals(Arrays.asList("d", "f"), def);
163     }
164 
testAtomicAdds()165     public void testAtomicAdds() throws Exception {
166         testAddAllIsAtomic(new CopyOnWriteArrayList<Object>());
167     }
168 
testSubListAtomicAdds()169     public void testSubListAtomicAdds() throws Exception {
170         testAddAllIsAtomic(new CopyOnWriteArrayList<Object>().subList(0, 0));
171     }
172 
173     /**
174      * Attempts to observe {@code list} in the middle of an add. The RI's
175      * CopyOnWriteArrayList passes this test, but its sub list doesn't.
176      */
testAddAllIsAtomic(final List<Object> list)177     private void testAddAllIsAtomic(final List<Object> list) throws Exception {
178         final CountDownLatch done = new CountDownLatch(1);
179 
180         ExecutorService executor = Executors.newSingleThreadExecutor();
181         Future<?> future = executor.submit(new Runnable() {
182             @Override public void run() {
183                 while (done.getCount() > 0) {
184                     int listSize = list.size();
185                     assertEquals("addAll() not atomic; size=" + listSize, 0, listSize % 1000);
186                     Thread.yield();
187                 }
188             }
189         });
190         executor.shutdown();
191 
192         List<Object> toAdd = Arrays.asList(new Object[1000]);
193         for (int i = 0; i < 100; i++) {
194             list.addAll(toAdd);
195             list.clear();
196             Thread.yield();
197         }
198 
199         done.countDown();
200         future.get(); // this will throw the above exception
201     }
202 
testSubListAddIsAtEnd()203     public void testSubListAddIsAtEnd() {
204         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
205         list.addAll(Arrays.asList("a", "b", "c", "d", "e"));
206         List<String> bcd = list.subList(1, 4);
207         bcd.add("f");
208         assertEquals(Arrays.asList("a", "b", "c", "d", "f", "e"), list);
209         assertEquals(Arrays.asList("b", "c", "d", "f"), bcd);
210     }
211 
testSubListAddAll()212     public void testSubListAddAll() {
213         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
214         list.addAll(Arrays.asList("a", "b", "c", "d", "e"));
215         List<String> bcd = list.subList(1, 4);
216         bcd.addAll(1, Arrays.asList("f", "g", "h", "i"));
217         assertEquals(Arrays.asList("a", "b", "f", "g", "h", "i", "c", "d", "e"), list);
218         assertEquals(Arrays.asList("b", "f", "g", "h", "i", "c", "d"), bcd);
219     }
220 
testListIterator()221     public void testListIterator() {
222         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
223         list.addAll(Arrays.asList("a", "b", "c", "d", "e"));
224         ListIterator<String> i = list.listIterator(5);
225         list.clear();
226 
227         assertEquals(5, i.nextIndex());
228         assertEquals(4, i.previousIndex());
229         assertEquals("e", i.previous());
230         assertEquals(4, i.nextIndex());
231         assertEquals(3, i.previousIndex());
232         assertTrue(i.hasNext());
233         assertTrue(i.hasPrevious());
234         assertEquals("d", i.previous());
235         assertEquals(3, i.nextIndex());
236         assertEquals(2, i.previousIndex());
237         assertTrue(i.hasNext());
238         assertTrue(i.hasPrevious());
239         assertEquals("c", i.previous());
240         assertEquals(2, i.nextIndex());
241         assertEquals(1, i.previousIndex());
242         assertTrue(i.hasNext());
243         assertTrue(i.hasPrevious());
244         assertEquals("b", i.previous());
245         assertEquals(1, i.nextIndex());
246         assertEquals(0, i.previousIndex());
247         assertTrue(i.hasNext());
248         assertTrue(i.hasPrevious());
249         assertEquals("a", i.previous());
250         assertEquals(0, i.nextIndex());
251         assertEquals(-1, i.previousIndex());
252         assertTrue(i.hasNext());
253         assertFalse(i.hasPrevious());
254         try {
255             i.previous();
256             fail();
257         } catch (NoSuchElementException expected) {
258         }
259     }
260 
testSerialize()261     public void testSerialize() {
262         String s = "aced0005737200296a6176612e7574696c2e636f6e63757272656e742e436f70"
263                 + "794f6e577269746541727261794c697374785d9fd546ab90c3030000787077040"
264                 + "0000005740001617400016274000163707400016578";
265 
266         List<String> contents = Arrays.asList("a", "b", "c", null, "e");
267         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>(contents);
268 
269         new SerializationTester<CopyOnWriteArrayList<String>>(list, s).test();
270     }
271 
272     /**
273      * Test that we don't retain the array returned by toArray() on the copy
274      * constructor. That array may not be of the required type!
275      */
testDoesNotRetainToArray()276     public void testDoesNotRetainToArray() {
277         String[] strings = { "a", "b", "c" };
278         List<String> asList = Arrays.asList(strings);
279         assertEquals(String[].class, asList.toArray().getClass());
280         CopyOnWriteArrayList<Object> objects = new CopyOnWriteArrayList<Object>(asList);
281         objects.add(Boolean.TRUE);
282     }
283 
test_forEachRemaining_iterator()284     public void test_forEachRemaining_iterator() throws Exception {
285         ForEachRemainingTester.test_forEachRemaining(
286                 new CopyOnWriteArrayList<>(), new String[] { "foo", "bar", "baz"});
287         ForEachRemainingTester.test_forEachRemaining_NPE(
288                 new CopyOnWriteArrayList<>(), new String[] {});
289     }
290 
test_forEachRemaining_CME()291     public void test_forEachRemaining_CME() throws Exception {
292         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
293         list.add("foo");
294         list.add("bar");
295         list.add("baz");
296         // Shouldn't throw a CME.
297         list.iterator().forEachRemaining(s -> list.add(s));
298     }
299 
test_replaceAll()300     public void test_replaceAll() {
301         List<Double> l = new CopyOnWriteArrayList<>(new Double[] {5.0, 2.0, -3.0});
302         l.replaceAll(v -> v * 2);
303         assertEquals(10.0, l.get(0));
304         assertEquals(4.0, l.get(1));
305         assertEquals(-6.0, l.get(2));
306 
307         // check for null operator
308         try {
309             l.replaceAll(null);
310             fail();
311         } catch (NullPointerException expected) {
312         }
313     }
314 
test_sort()315     public void test_sort() {
316         List<Double> l = new CopyOnWriteArrayList<>(new Double[] {5.0, 2.0, -3.0});
317         l.sort((v1, v2) -> v1.compareTo(v2));
318         assertEquals(-3.0, l.get(0));
319         assertEquals(2.0, l.get(1));
320         assertEquals(5.0, l.get(2));
321     }
322 
test_forEach()323     public void test_forEach() {
324         List<Double> l = new CopyOnWriteArrayList<>(new Double[] {10.0, 5.0, 2.0});
325         List<Double> replica = new ArrayList<>();
326         l.forEach(k -> replica.add(k));
327         assertEquals(10.0, replica.get(0));
328         assertEquals(5.0, replica.get(1));
329         assertEquals(2.0, replica.get(2));
330         assertEquals(3, replica.size());
331 
332         // Verifying the original content of the list
333         assertEquals(10.0, l.get(0));
334         assertEquals(5.0, l.get(1));
335         assertEquals(2.0, l.get(2));
336 
337         try {
338             l.forEach(null);
339             fail();
340         } catch (NullPointerException expected) {
341         }
342     }
343 
test_subList_replaceAll()344     public void test_subList_replaceAll() {
345         List<Double> l = new CopyOnWriteArrayList<>(new Double[] {5.0, 2.0, -3.0}).subList(0, 3);
346         l.replaceAll(v -> v * 2);
347         assertEquals(10.0, l.get(0));
348         assertEquals(4.0, l.get(1));
349         assertEquals(-6.0, l.get(2));
350 
351         // check for null operator
352         try {
353             l.replaceAll(null);
354             fail();
355         } catch (NullPointerException expected) {
356         }
357 
358         CopyOnWriteArrayList completeList = new CopyOnWriteArrayList<Integer>();
359         completeList.add(1);
360         completeList.add(2);
361         completeList.add(3);
362         completeList.add(4);
363         completeList.add(5);
364         List<Integer> subList = completeList.subList(1, 3);
365         subList.replaceAll(k -> k + 10);
366         assertEquals(12, (int)subList.get(0));
367         assertEquals(13, (int)subList.get(1));
368         assertEquals(1, (int)completeList.get(0));
369         assertEquals(12, (int)completeList.get(1));
370         assertEquals(13, (int)completeList.get(2));
371         assertEquals(4, (int)completeList.get(3));
372         assertEquals(5, (int)completeList.get(4));
373     }
374 
test_subList_sort()375     public void test_subList_sort() {
376         List<Double> l = new CopyOnWriteArrayList<>(new Double[] {5.0, 2.0, -3.0}).subList(0, 3);
377         l.sort((v1, v2) -> v1.compareTo(v2));
378         assertEquals(-3.0, l.get(0));
379         assertEquals(2.0, l.get(1));
380         assertEquals(5.0, l.get(2));
381 
382         CopyOnWriteArrayList completeList = new CopyOnWriteArrayList<Integer>();
383         completeList.add(10);
384         completeList.add(56);
385         completeList.add(22);
386         completeList.add(2);
387         completeList.add(9);
388         completeList.add(12);
389 
390         List<Integer> subList = completeList.subList(2, 5);
391         subList.sort((k1, k2) -> k1.compareTo(k2));
392 
393         //subList before sort -> 56, 22, 2, 9
394         //subList after sort -> 2, 9, 22, 56
395 
396         assertEquals(2, (int)subList.get(0));
397         assertEquals(9, (int)subList.get(1));
398         assertEquals(22, (int)subList.get(2));
399         assertEquals(10, (int)completeList.get(0));
400         assertEquals(56, (int)completeList.get(1));
401         assertEquals(2, (int)completeList.get(2));
402         assertEquals(9, (int)completeList.get(3));
403         assertEquals(22, (int)completeList.get(4));
404         assertEquals(12, (int)completeList.get(5));
405     }
406 
test_subList_forEach()407     public void test_subList_forEach() {
408         List<Double> l = new CopyOnWriteArrayList<>(new Double[]{10.0, 5.0, 2.0, -3.0, 7.0, 12.0})
409                 .subList(1, 4);
410         List<Double> replica = new ArrayList<>();
411         l.forEach(k -> replica.add(k));
412         assertEquals(5.0, replica.get(0));
413         assertEquals(2.0, replica.get(1));
414         assertEquals(-3.0, replica.get(2));
415         assertEquals(3, replica.size());
416 
417         // Verifying the original content of the list
418         assertEquals(5.0, l.get(0));
419         assertEquals(2.0, l.get(1));
420         assertEquals(-3.0, l.get(2));
421 
422         try {
423             l.forEach(null);
424             fail();
425         } catch (NullPointerException expected) {
426         }
427     }
428 }
429