1/* 2 * Copyright 2016 Google, Inc. All Rights Reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 24/* 25 * @test 26 * @bug 8146568 27 * @summary brittle white box test of internal array management 28 * @modules java.base/java.util:open 29 * @run testng ArrayManagement 30 */ 31 32import java.lang.reflect.Field; 33import java.util.AbstractList; 34import java.util.ArrayList; 35import java.util.Collections; 36import java.util.List; 37import java.util.SplittableRandom; 38 39import org.testng.annotations.Test; 40import static org.testng.Assert.*; 41 42public class ArrayManagement { 43 static final int DEFAULT_CAPACITY = 10; 44 static final Field ELEMENT_DATA; 45 static final Field MODCOUNT; 46 static final SplittableRandom rnd = new SplittableRandom(); 47 48 static { 49 try { 50 ELEMENT_DATA = ArrayList.class.getDeclaredField("elementData"); 51 ELEMENT_DATA.setAccessible(true); 52 MODCOUNT = AbstractList.class.getDeclaredField("modCount"); 53 MODCOUNT.setAccessible(true); 54 } catch (ReflectiveOperationException huh) { 55 throw new AssertionError(huh); 56 } 57 } 58 59 static Object[] elementData(ArrayList<?> list) { 60 try { 61 return (Object[]) ELEMENT_DATA.get(list); 62 } catch (ReflectiveOperationException huh) { 63 throw new AssertionError(huh); 64 } 65 } 66 67 static int modCount(ArrayList<?> list) { 68 try { 69 return MODCOUNT.getInt(list); 70 } catch (ReflectiveOperationException huh) { 71 throw new AssertionError(huh); 72 } 73 } 74 75 static int capacity(ArrayList<?> list) { 76 return elementData(list).length; 77 } 78 79 static int newCapacity(int oldCapacity) { 80 return oldCapacity + (oldCapacity >> 1); 81 } 82 83 static void ensureCapacity(ArrayList<Object> list, int capacity) { 84 int oldCapacity = capacity(list); 85 int oldModCount = modCount(list); 86 list.ensureCapacity(capacity); 87 assertTrue(capacity(list) >= capacity || capacity(list) == 0); 88 assertEquals(modCount(list), 89 (capacity(list) == oldCapacity) 90 ? oldModCount 91 : oldModCount + 1); 92 } 93 94 static List<Object> singletonList() { 95 return Collections.singletonList(Boolean.TRUE); 96 } 97 98 /** Opportunistically randomly test various add operations. */ 99 static void addOneElement(ArrayList<Object> list) { 100 int size = list.size(); 101 int modCount = modCount(list); 102 switch (rnd.nextInt(4)) { 103 case 0: assertTrue(list.add(Boolean.TRUE)); break; 104 case 1: list.add(size, Boolean.TRUE); break; 105 case 2: assertTrue(list.addAll(singletonList())); break; 106 case 3: assertTrue(list.addAll(size, singletonList())); break; 107 default: throw new AssertionError(); 108 } 109 assertEquals(modCount(list), modCount + 1); 110 assertEquals(list.size(), size + 1); 111 } 112 113 @Test public void defaultCapacity() { 114 ArrayList<Object> list = new ArrayList<>(); 115 assertEquals(capacity(new ArrayList<Object>()), 0); 116 for (int i = 0; i < DEFAULT_CAPACITY; i++) { 117 addOneElement(list); 118 assertEquals(capacity(list), DEFAULT_CAPACITY); 119 } 120 addOneElement(list); 121 assertEquals(capacity(list), newCapacity(DEFAULT_CAPACITY)); 122 } 123 124 @Test public void defaultCapacityEnsureCapacity() { 125 ArrayList<Object> list = new ArrayList<>(); 126 for (int i = 0; i <= DEFAULT_CAPACITY; i++) { 127 ensureCapacity(list, i); // no-op! 128 assertEquals(capacity(list), 0); 129 } 130 for (int i = 0; i < DEFAULT_CAPACITY; i++) { 131 addOneElement(list); 132 assertEquals(capacity(list), DEFAULT_CAPACITY); 133 } 134 addOneElement(list); 135 assertEquals(capacity(list), newCapacity(DEFAULT_CAPACITY)); 136 { 137 int capacity = capacity(list); 138 ensureCapacity(list, capacity + 1); 139 assertEquals(capacity(list), newCapacity(capacity)); 140 } 141 { 142 int capacity = capacity(list); 143 ensureCapacity(list, 3 * capacity); 144 assertEquals(capacity(list), 3 * capacity); 145 } 146 } 147 148 @Test public void ensureCapacityBeyondDefaultCapacity() { 149 ArrayList<Object> list = new ArrayList<>(); 150 list.ensureCapacity(DEFAULT_CAPACITY + 1); 151 assertEquals(capacity(list), DEFAULT_CAPACITY + 1); 152 for (int i = 0; i < DEFAULT_CAPACITY + 1; i++) { 153 addOneElement(list); 154 assertEquals(capacity(list), DEFAULT_CAPACITY + 1); 155 } 156 addOneElement(list); 157 assertEquals(capacity(list), newCapacity(DEFAULT_CAPACITY + 1)); 158 } 159 160 @Test public void explicitZeroCapacity() { 161 ArrayList<Object> list = new ArrayList<>(0); 162 assertEquals(capacity(list), 0); 163 addOneElement(list); 164 assertEquals(capacity(list), 1); 165 addOneElement(list); 166 assertEquals(capacity(list), 2); 167 addOneElement(list); 168 assertEquals(capacity(list), 3); 169 addOneElement(list); 170 assertEquals(capacity(list), 4); 171 addOneElement(list); 172 assertEquals(capacity(list), 6); 173 addOneElement(list); 174 assertEquals(capacity(list), 6); 175 addOneElement(list); 176 assertEquals(capacity(list), 9); 177 list.clear(); 178 assertEquals(capacity(list), 9); 179 } 180 181 @Test public void explicitLargeCapacity() { 182 int n = DEFAULT_CAPACITY * 3; 183 ArrayList<Object> list = new ArrayList<>(n); 184 assertEquals(capacity(list), n); 185 ensureCapacity(list, 0); 186 ensureCapacity(list, n); 187 for (int i = 0; i < n; i++) addOneElement(list); 188 assertEquals(capacity(list), n); 189 190 addOneElement(list); 191 assertEquals(capacity(list), newCapacity(n)); 192 } 193 194 @Test public void emptyArraysAreShared() { 195 assertSame(elementData(new ArrayList<Object>()), 196 elementData(new ArrayList<Object>())); 197 assertSame(elementData(new ArrayList<Object>(0)), 198 elementData(new ArrayList<Object>(0))); 199 } 200 201 @Test public void emptyArraysDifferBetweenDefaultAndExplicit() { 202 assertNotSame(elementData(new ArrayList<Object>()), 203 elementData(new ArrayList<Object>(0))); 204 } 205 206 @Test public void negativeCapacity() { 207 for (int capacity : new int[] { -1, Integer.MIN_VALUE }) { 208 try { 209 new ArrayList<Object>(capacity); 210 fail("should throw"); 211 } catch (IllegalArgumentException success) {} 212 } 213 } 214} 215