Home | History | Annotate | Download | only in concurrent
      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.Arrays;
     20 import java.util.ConcurrentModificationException;
     21 import java.util.Iterator;
     22 import java.util.List;
     23 import java.util.ListIterator;
     24 import java.util.NoSuchElementException;
     25 import java.util.concurrent.CopyOnWriteArrayList;
     26 import java.util.concurrent.CountDownLatch;
     27 import java.util.concurrent.ExecutorService;
     28 import java.util.concurrent.Executors;
     29 import java.util.concurrent.Future;
     30 import junit.framework.TestCase;
     31 import libcore.util.SerializationTester;
     32 
     33 public final class CopyOnWriteArrayListTest extends TestCase {
     34 
     35     public void testIteratorAndNonStructuralChanges() {
     36         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
     37         list.addAll(Arrays.asList("a", "b", "c", "d", "e"));
     38         Iterator<String> abcde = list.iterator();
     39         assertEquals("a", abcde.next());
     40         list.set(1, "B");
     41         assertEquals("b", abcde.next());
     42         assertEquals("c", abcde.next());
     43         assertEquals("d", abcde.next());
     44         assertEquals("e", abcde.next());
     45     }
     46 
     47     /**
     48      * The sub list throws on non-structural changes, even though that disagrees
     49      * with the subList() documentation which suggests that only size-changing
     50      * operations will trigger ConcurrentModificationException.
     51      */
     52     public void testSubListAndNonStructuralChanges() {
     53         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
     54         list.addAll(Arrays.asList("a", "b", "c", "d", "e"));
     55         List<String> bcd = list.subList(1, 4);
     56         list.set(2, "C");
     57         try {
     58             bcd.get(1);
     59             fail();
     60         } catch (ConcurrentModificationException expected) {
     61         }
     62     }
     63 
     64     public void testSubListAndStructuralChanges() {
     65         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
     66         list.addAll(Arrays.asList("a", "b", "c", "d", "e"));
     67         List<String> bcd = list.subList(1, 4);
     68         list.clear();
     69         try {
     70             bcd.get(1);
     71             fail();
     72         } catch (ConcurrentModificationException expected) {
     73         }
     74     }
     75 
     76     public void testSubListAndSizePreservingStructuralChanges() {
     77         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
     78         list.addAll(Arrays.asList("a", "b", "c", "d", "e"));
     79         List<String> bcd = list.subList(1, 4);
     80         list.clear();
     81         list.addAll(Arrays.asList("A", "B", "C", "D", "E"));
     82         try {
     83             bcd.get(1);
     84             fail();
     85         } catch (ConcurrentModificationException expected) {
     86         }
     87     }
     88 
     89     public void testRemoveAll() {
     90         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
     91         list.addAll(Arrays.asList("a", "b", "c", "d", "e"));
     92 
     93         list.removeAll(Arrays.asList());
     94         assertEquals(Arrays.asList("a", "b", "c", "d", "e"), list);
     95 
     96         list.removeAll(Arrays.asList("e"));
     97         assertEquals(Arrays.asList("a", "b", "c", "d"), list);
     98 
     99         list.removeAll(Arrays.asList("b", "c"));
    100         assertEquals(Arrays.asList("a", "d"), list);
    101     }
    102 
    103     public void testSubListClear() {
    104         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
    105         list.addAll(Arrays.asList("a", "b", "c", "d", "e"));
    106         List<String> bcd = list.subList(1, 4);
    107         bcd.clear();
    108         assertEquals(Arrays.asList("a", "e"), list);
    109         bcd.addAll(Arrays.asList("B", "C", "D"));
    110         assertEquals(Arrays.asList("a", "B", "C", "D", "e"), list);
    111     }
    112 
    113     public void testSubListClearWhenEmpty() {
    114         new CopyOnWriteArrayList<String>().subList(0, 0).clear(); // the RI fails here
    115     }
    116 
    117     public void testSubListIteratorGetsSnapshot() {
    118         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
    119         list.addAll(Arrays.asList("a", "b", "c", "d", "e"));
    120         Iterator<String> bcd = list.subList(1, 4).iterator();
    121         list.clear();
    122         assertEquals("b", bcd.next());
    123         assertEquals("c", bcd.next());
    124         assertEquals("d", bcd.next());
    125         assertFalse(bcd.hasNext());
    126     }
    127 
    128     public void testSubListRemoveByValue() {
    129         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
    130         list.addAll(Arrays.asList("a", "b", "c", "d", "e"));
    131         List<String> bcd = list.subList(1, 4);
    132         bcd.remove("c"); // the RI fails here
    133         assertEquals(Arrays.asList("b", "d"), bcd);
    134         assertEquals(Arrays.asList("a", "b", "d", "e"), list);
    135     }
    136 
    137     public void testSubListRemoveByIndex() {
    138         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
    139         list.addAll(Arrays.asList("a", "b", "c", "d", "e"));
    140         List<String> bcd = list.subList(1, 4);
    141         bcd.remove(1);
    142         assertEquals(Arrays.asList("b", "d"), bcd);
    143         assertEquals(Arrays.asList("a", "b", "d", "e"), list);
    144     }
    145 
    146     public void testSubListRetainAll() {
    147         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
    148         list.addAll(Arrays.asList("a", "b", "c", "d", "e", "f", "g", "h", "i"));
    149         List<String> def = list.subList(3, 6);
    150         def.retainAll(Arrays.asList("c", "e", "h")); // the RI fails here
    151         assertEquals(Arrays.asList("a", "b", "c", "e", "g", "h", "i"), list);
    152         assertEquals(Arrays.asList("e"), def);
    153     }
    154 
    155     public void testSubListRemoveAll() {
    156         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
    157         list.addAll(Arrays.asList("a", "b", "c", "d", "e", "f", "g", "h", "i"));
    158         List<String> def = list.subList(3, 6);
    159         def.removeAll(Arrays.asList("c", "e", "h"));  // the RI fails here
    160         assertEquals(Arrays.asList("a", "b", "c", "d", "f", "g", "h", "i"), list);
    161         assertEquals(Arrays.asList("d", "f"), def);
    162     }
    163 
    164     public void testAtomicAdds() throws Exception {
    165         testAddAllIsAtomic(new CopyOnWriteArrayList<Object>());
    166     }
    167 
    168     public void testSubListAtomicAdds() throws Exception {
    169         testAddAllIsAtomic(new CopyOnWriteArrayList<Object>().subList(0, 0));
    170     }
    171 
    172     /**
    173      * Attempts to observe {@code list} in the middle of an add. The RI's
    174      * CopyOnWriteArrayList passes this test, but its sub list doesn't.
    175      */
    176     private void testAddAllIsAtomic(final List<Object> list) throws Exception {
    177         final CountDownLatch done = new CountDownLatch(1);
    178 
    179         ExecutorService executor = Executors.newSingleThreadExecutor();
    180         Future<?> future = executor.submit(new Runnable() {
    181             @Override public void run() {
    182                 while (done.getCount() > 0) {
    183                     int listSize = list.size();
    184                     assertEquals("addAll() not atomic; size=" + listSize, 0, listSize % 1000);
    185                     Thread.yield();
    186                 }
    187             }
    188         });
    189         executor.shutdown();
    190 
    191         List<Object> toAdd = Arrays.asList(new Object[1000]);
    192         for (int i = 0; i < 100; i++) {
    193             list.addAll(toAdd);
    194             list.clear();
    195             Thread.yield();
    196         }
    197 
    198         done.countDown();
    199         future.get(); // this will throw the above exception
    200     }
    201 
    202     public void testSubListAddIsAtEnd() {
    203         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
    204         list.addAll(Arrays.asList("a", "b", "c", "d", "e"));
    205         List<String> bcd = list.subList(1, 4);
    206         bcd.add("f");
    207         assertEquals(Arrays.asList("a", "b", "c", "d", "f", "e"), list);
    208         assertEquals(Arrays.asList("b", "c", "d", "f"), bcd);
    209     }
    210 
    211     public void testSubListAddAll() {
    212         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
    213         list.addAll(Arrays.asList("a", "b", "c", "d", "e"));
    214         List<String> bcd = list.subList(1, 4);
    215         bcd.addAll(1, Arrays.asList("f", "g", "h", "i"));
    216         assertEquals(Arrays.asList("a", "b", "f", "g", "h", "i", "c", "d", "e"), list);
    217         assertEquals(Arrays.asList("b", "f", "g", "h", "i", "c", "d"), bcd);
    218     }
    219 
    220     public void testListIterator() {
    221         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
    222         list.addAll(Arrays.asList("a", "b", "c", "d", "e"));
    223         ListIterator<String> i = list.listIterator(5);
    224         list.clear();
    225 
    226         assertEquals(5, i.nextIndex());
    227         assertEquals(4, i.previousIndex());
    228         assertEquals("e", i.previous());
    229         assertEquals(4, i.nextIndex());
    230         assertEquals(3, i.previousIndex());
    231         assertTrue(i.hasNext());
    232         assertTrue(i.hasPrevious());
    233         assertEquals("d", i.previous());
    234         assertEquals(3, i.nextIndex());
    235         assertEquals(2, i.previousIndex());
    236         assertTrue(i.hasNext());
    237         assertTrue(i.hasPrevious());
    238         assertEquals("c", i.previous());
    239         assertEquals(2, i.nextIndex());
    240         assertEquals(1, i.previousIndex());
    241         assertTrue(i.hasNext());
    242         assertTrue(i.hasPrevious());
    243         assertEquals("b", i.previous());
    244         assertEquals(1, i.nextIndex());
    245         assertEquals(0, i.previousIndex());
    246         assertTrue(i.hasNext());
    247         assertTrue(i.hasPrevious());
    248         assertEquals("a", i.previous());
    249         assertEquals(0, i.nextIndex());
    250         assertEquals(-1, i.previousIndex());
    251         assertTrue(i.hasNext());
    252         assertFalse(i.hasPrevious());
    253         try {
    254             i.previous();
    255             fail();
    256         } catch (NoSuchElementException expected) {
    257         }
    258     }
    259 
    260     public void testSerialize() {
    261         String s = "aced0005737200296a6176612e7574696c2e636f6e63757272656e742e436f70"
    262                 + "794f6e577269746541727261794c697374785d9fd546ab90c3030000787077040"
    263                 + "0000005740001617400016274000163707400016578";
    264 
    265         List<String> contents = Arrays.asList("a", "b", "c", null, "e");
    266         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>(contents);
    267 
    268         new SerializationTester<CopyOnWriteArrayList<String>>(list, s).test();
    269     }
    270 
    271     /**
    272      * Test that we don't retain the array returned by toArray() on the copy
    273      * constructor. That array may not be of the required type!
    274      */
    275     public void testDoesNotRetainToArray() {
    276         String[] strings = { "a", "b", "c" };
    277         List<String> asList = Arrays.asList(strings);
    278         assertEquals(String[].class, asList.toArray().getClass());
    279         CopyOnWriteArrayList<Object> objects = new CopyOnWriteArrayList<Object>(asList);
    280         objects.add(Boolean.TRUE);
    281     }
    282 }
    283