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