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 
32 package test.java.util.ArrayList;
33 
34 import java.lang.reflect.Field;
35 import java.util.AbstractList;
36 import java.util.ArrayList;
37 import java.util.Collections;
38 import java.util.List;
39 import java.util.SplittableRandom;
40 
41 import org.testng.annotations.Test;
42 import static org.testng.Assert.*;
43 
44 public class ArrayManagement {
45     static final int DEFAULT_CAPACITY = 10;
46     static final Field ELEMENT_DATA;
47     static final Field MODCOUNT;
48     static final SplittableRandom rnd = new SplittableRandom();
49 
50     static {
51         try {
52             ELEMENT_DATA = ArrayList.class.getDeclaredField("elementData");
53             ELEMENT_DATA.setAccessible(true);
54             MODCOUNT = AbstractList.class.getDeclaredField("modCount");
55             MODCOUNT.setAccessible(true);
56         } catch (ReflectiveOperationException huh) {
57             throw new AssertionError(huh);
58         }
59     }
60 
elementData(ArrayList<?> list)61     static Object[] elementData(ArrayList<?> list) {
62         try {
63             return (Object[]) ELEMENT_DATA.get(list);
64         } catch (ReflectiveOperationException huh) {
65             throw new AssertionError(huh);
66         }
67     }
68 
modCount(ArrayList<?> list)69     static int modCount(ArrayList<?> list) {
70         try {
71             return MODCOUNT.getInt(list);
72         } catch (ReflectiveOperationException huh) {
73             throw new AssertionError(huh);
74         }
75     }
76 
capacity(ArrayList<?> list)77     static int capacity(ArrayList<?> list) {
78         return elementData(list).length;
79     }
80 
newCapacity(int oldCapacity)81     static int newCapacity(int oldCapacity) {
82         return oldCapacity + (oldCapacity >> 1);
83     }
84 
ensureCapacity(ArrayList<Object> list, int capacity)85     static void ensureCapacity(ArrayList<Object> list, int capacity) {
86         int oldCapacity = capacity(list);
87         int oldModCount = modCount(list);
88         list.ensureCapacity(capacity);
89         assertTrue(capacity(list) >= capacity || capacity(list) == 0);
90         assertEquals(modCount(list),
91                      (capacity(list) == oldCapacity)
92                      ? oldModCount
93                      : oldModCount + 1);
94     }
95 
singletonList()96     static List<Object> singletonList() {
97         return Collections.singletonList(Boolean.TRUE);
98     }
99 
100     /** Opportunistically randomly test various add operations. */
addOneElement(ArrayList<Object> list)101     static void addOneElement(ArrayList<Object> list) {
102         int size = list.size();
103         int modCount = modCount(list);
104         switch (rnd.nextInt(4)) {
105         case 0: assertTrue(list.add(Boolean.TRUE)); break;
106         case 1: list.add(size, Boolean.TRUE); break;
107         case 2: assertTrue(list.addAll(singletonList())); break;
108         case 3: assertTrue(list.addAll(size, singletonList())); break;
109         default: throw new AssertionError();
110         }
111         assertEquals(modCount(list), modCount + 1);
112         assertEquals(list.size(), size + 1);
113     }
114 
defaultCapacity()115     @Test public void defaultCapacity() {
116         ArrayList<Object> list = new ArrayList<>();
117         assertEquals(capacity(new ArrayList<Object>()), 0);
118         for (int i = 0; i < DEFAULT_CAPACITY; i++) {
119             addOneElement(list);
120             assertEquals(capacity(list), DEFAULT_CAPACITY);
121         }
122         addOneElement(list);
123         assertEquals(capacity(list), newCapacity(DEFAULT_CAPACITY));
124     }
125 
defaultCapacityEnsureCapacity()126     @Test public void defaultCapacityEnsureCapacity() {
127         ArrayList<Object> list = new ArrayList<>();
128         for (int i = 0; i <= DEFAULT_CAPACITY; i++) {
129             ensureCapacity(list, i);     // no-op!
130             assertEquals(capacity(list), 0);
131         }
132         for (int i = 0; i < DEFAULT_CAPACITY; i++) {
133             addOneElement(list);
134             assertEquals(capacity(list), DEFAULT_CAPACITY);
135         }
136         addOneElement(list);
137         assertEquals(capacity(list), newCapacity(DEFAULT_CAPACITY));
138         {
139             int capacity = capacity(list);
140             ensureCapacity(list, capacity + 1);
141             assertEquals(capacity(list), newCapacity(capacity));
142         }
143         {
144             int capacity = capacity(list);
145             ensureCapacity(list, 3 * capacity);
146             assertEquals(capacity(list), 3 * capacity);
147         }
148     }
149 
ensureCapacityBeyondDefaultCapacity()150     @Test public void ensureCapacityBeyondDefaultCapacity() {
151         ArrayList<Object> list = new ArrayList<>();
152         list.ensureCapacity(DEFAULT_CAPACITY + 1);
153         assertEquals(capacity(list), DEFAULT_CAPACITY + 1);
154         for (int i = 0; i < DEFAULT_CAPACITY + 1; i++) {
155             addOneElement(list);
156             assertEquals(capacity(list), DEFAULT_CAPACITY + 1);
157         }
158         addOneElement(list);
159         assertEquals(capacity(list), newCapacity(DEFAULT_CAPACITY + 1));
160     }
161 
explicitZeroCapacity()162     @Test public void explicitZeroCapacity() {
163         ArrayList<Object> list = new ArrayList<>(0);
164         assertEquals(capacity(list), 0);
165         addOneElement(list);
166         assertEquals(capacity(list), 1);
167         addOneElement(list);
168         assertEquals(capacity(list), 2);
169         addOneElement(list);
170         assertEquals(capacity(list), 3);
171         addOneElement(list);
172         assertEquals(capacity(list), 4);
173         addOneElement(list);
174         assertEquals(capacity(list), 6);
175         addOneElement(list);
176         assertEquals(capacity(list), 6);
177         addOneElement(list);
178         assertEquals(capacity(list), 9);
179         list.clear();
180         assertEquals(capacity(list), 9);
181     }
182 
explicitLargeCapacity()183     @Test public void explicitLargeCapacity() {
184         int n = DEFAULT_CAPACITY * 3;
185         ArrayList<Object> list = new ArrayList<>(n);
186         assertEquals(capacity(list), n);
187         ensureCapacity(list, 0);
188         ensureCapacity(list, n);
189         for (int i = 0; i < n; i++) addOneElement(list);
190         assertEquals(capacity(list), n);
191 
192         addOneElement(list);
193         assertEquals(capacity(list), newCapacity(n));
194     }
195 
emptyArraysAreShared()196     @Test public void emptyArraysAreShared() {
197         assertSame(elementData(new ArrayList<Object>()),
198                    elementData(new ArrayList<Object>()));
199         assertSame(elementData(new ArrayList<Object>(0)),
200                    elementData(new ArrayList<Object>(0)));
201     }
202 
emptyArraysDifferBetweenDefaultAndExplicit()203     @Test public void emptyArraysDifferBetweenDefaultAndExplicit() {
204         assertNotSame(elementData(new ArrayList<Object>()),
205                       elementData(new ArrayList<Object>(0)));
206     }
207 
negativeCapacity()208     @Test public void negativeCapacity() {
209         for (int capacity : new int[] { -1, Integer.MIN_VALUE }) {
210             try {
211                 new ArrayList<Object>(capacity);
212                 fail("should throw");
213             } catch (IllegalArgumentException success) {}
214         }
215     }
216 }
217