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
