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
17package libcore.java.util.concurrent;
18
19import java.util.ArrayList;
20import java.util.Arrays;
21import java.util.ConcurrentModificationException;
22import java.util.Iterator;
23import java.util.List;
24import java.util.ListIterator;
25import java.util.NoSuchElementException;
26import java.util.concurrent.CopyOnWriteArrayList;
27import java.util.concurrent.CountDownLatch;
28import java.util.concurrent.ExecutorService;
29import java.util.concurrent.Executors;
30import java.util.concurrent.Future;
31import junit.framework.TestCase;
32import libcore.java.util.ForEachRemainingTester;
33import libcore.libcore.util.SerializationTester;
34public final class CopyOnWriteArrayListTest extends TestCase {
35
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     */
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
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
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
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
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
114    public void testSubListClearWhenEmpty() {
115        new CopyOnWriteArrayList<String>().subList(0, 0).clear(); // the RI fails here
116    }
117
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
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
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
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
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
165    public void testAtomicAdds() throws Exception {
166        testAddAllIsAtomic(new CopyOnWriteArrayList<Object>());
167    }
168
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     */
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
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
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
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
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     */
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
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
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
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
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
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
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
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
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