1 /*
2 * Copyright (c) 1997, 2018, Oracle and/or its affiliates. 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. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27
28 import java.util.function.Consumer;
29 import java.util.function.Predicate;
30 import java.util.function.UnaryOperator;
31 import jdk.internal.access.SharedSecrets;
32
33 /**
34 * Resizable-array implementation of the {@code List} interface. Implements
35 * all optional list operations, and permits all elements, including
36 * {@code null}. In addition to implementing the {@code List} interface,
37 * this class provides methods to manipulate the size of the array that is
38 * used internally to store the list. (This class is roughly equivalent to
39 * {@code Vector}, except that it is unsynchronized.)
40 *
41 * <p>The {@code size}, {@code isEmpty}, {@code get}, {@code set},
42 * {@code iterator}, and {@code listIterator} operations run in constant
43 * time. The {@code add} operation runs in <i>amortized constant time</i>,
44 * that is, adding n elements requires O(n) time. All of the other operations
45 * run in linear time (roughly speaking). The constant factor is low compared
46 * to that for the {@code LinkedList} implementation.
47 *
48 * <p>Each {@code ArrayList} instance has a <i>capacity</i>. The capacity is
49 * the size of the array used to store the elements in the list. It is always
50 * at least as large as the list size. As elements are added to an ArrayList,
51 * its capacity grows automatically. The details of the growth policy are not
202 }
203 }
204
205 /**
206 * Increases the capacity of this {@code ArrayList} instance, if
207 * necessary, to ensure that it can hold at least the number of elements
208 * specified by the minimum capacity argument.
209 *
210 * @param minCapacity the desired minimum capacity
211 */
212 public void ensureCapacity(int minCapacity) {
213 if (minCapacity > elementData.length
214 && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
215 && minCapacity <= DEFAULT_CAPACITY)) {
216 modCount++;
217 grow(minCapacity);
218 }
219 }
220
221 /**
222 * The maximum size of array to allocate (unless necessary).
223 * Some VMs reserve some header words in an array.
224 * Attempts to allocate larger arrays may result in
225 * OutOfMemoryError: Requested array size exceeds VM limit
226 */
227 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
228
229 /**
230 * Increases the capacity to ensure that it can hold at least the
231 * number of elements specified by the minimum capacity argument.
232 *
233 * @param minCapacity the desired minimum capacity
234 * @throws OutOfMemoryError if minCapacity is less than zero
235 */
236 private Object[] grow(int minCapacity) {
237 return elementData = Arrays.copyOf(elementData,
238 newCapacity(minCapacity));
239 }
240
241 private Object[] grow() {
242 return grow(size + 1);
243 }
244
245 /**
246 * Returns a capacity at least as large as the given minimum capacity.
247 * Returns the current capacity increased by 50% if that suffices.
248 * Will not return a capacity greater than MAX_ARRAY_SIZE unless
249 * the given minimum capacity is greater than MAX_ARRAY_SIZE.
250 *
251 * @param minCapacity the desired minimum capacity
252 * @throws OutOfMemoryError if minCapacity is less than zero
253 */
254 private int newCapacity(int minCapacity) {
255 // overflow-conscious code
256 int oldCapacity = elementData.length;
257 int newCapacity = oldCapacity + (oldCapacity >> 1);
258 if (newCapacity - minCapacity <= 0) {
259 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
260 return Math.max(DEFAULT_CAPACITY, minCapacity);
261 if (minCapacity < 0) // overflow
262 throw new OutOfMemoryError();
263 return minCapacity;
264 }
265 return (newCapacity - MAX_ARRAY_SIZE <= 0)
266 ? newCapacity
267 : hugeCapacity(minCapacity);
268 }
269
270 private static int hugeCapacity(int minCapacity) {
271 if (minCapacity < 0) // overflow
272 throw new OutOfMemoryError();
273 return (minCapacity > MAX_ARRAY_SIZE)
274 ? Integer.MAX_VALUE
275 : MAX_ARRAY_SIZE;
276 }
277
278 /**
279 * Returns the number of elements in this list.
280 *
281 * @return the number of elements in this list
282 */
283 public int size() {
284 return size;
285 }
286
287 /**
288 * Returns {@code true} if this list contains no elements.
289 *
290 * @return {@code true} if this list contains no elements
291 */
292 public boolean isEmpty() {
293 return size == 0;
294 }
295
|
1 /*
2 * Copyright (c) 1997, 2019, Oracle and/or its affiliates. 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. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27
28 import java.util.function.Consumer;
29 import java.util.function.Predicate;
30 import java.util.function.UnaryOperator;
31 import jdk.internal.access.SharedSecrets;
32 import jdk.internal.util.ArraysSupport;
33
34 /**
35 * Resizable-array implementation of the {@code List} interface. Implements
36 * all optional list operations, and permits all elements, including
37 * {@code null}. In addition to implementing the {@code List} interface,
38 * this class provides methods to manipulate the size of the array that is
39 * used internally to store the list. (This class is roughly equivalent to
40 * {@code Vector}, except that it is unsynchronized.)
41 *
42 * <p>The {@code size}, {@code isEmpty}, {@code get}, {@code set},
43 * {@code iterator}, and {@code listIterator} operations run in constant
44 * time. The {@code add} operation runs in <i>amortized constant time</i>,
45 * that is, adding n elements requires O(n) time. All of the other operations
46 * run in linear time (roughly speaking). The constant factor is low compared
47 * to that for the {@code LinkedList} implementation.
48 *
49 * <p>Each {@code ArrayList} instance has a <i>capacity</i>. The capacity is
50 * the size of the array used to store the elements in the list. It is always
51 * at least as large as the list size. As elements are added to an ArrayList,
52 * its capacity grows automatically. The details of the growth policy are not
203 }
204 }
205
206 /**
207 * Increases the capacity of this {@code ArrayList} instance, if
208 * necessary, to ensure that it can hold at least the number of elements
209 * specified by the minimum capacity argument.
210 *
211 * @param minCapacity the desired minimum capacity
212 */
213 public void ensureCapacity(int minCapacity) {
214 if (minCapacity > elementData.length
215 && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
216 && minCapacity <= DEFAULT_CAPACITY)) {
217 modCount++;
218 grow(minCapacity);
219 }
220 }
221
222 /**
223 * Increases the capacity to ensure that it can hold at least the
224 * number of elements specified by the minimum capacity argument.
225 *
226 * @param minCapacity the desired minimum capacity
227 * @throws OutOfMemoryError if minCapacity is less than zero
228 */
229 private Object[] grow(int minCapacity) {
230 int oldCapacity = elementData.length;
231 if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
232 int newCapacity = ArraysSupport.calcLength(oldCapacity,
233 minCapacity - oldCapacity, /* minimum growth */
234 oldCapacity >> 1 /* preferred growth */);
235 return elementData = Arrays.copyOf(elementData, newCapacity);
236 } else {
237 return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
238 }
239 }
240
241 private Object[] grow() {
242 return grow(size + 1);
243 }
244
245 /**
246 * Returns the number of elements in this list.
247 *
248 * @return the number of elements in this list
249 */
250 public int size() {
251 return size;
252 }
253
254 /**
255 * Returns {@code true} if this list contains no elements.
256 *
257 * @return {@code true} if this list contains no elements
258 */
259 public boolean isEmpty() {
260 return size == 0;
261 }
262
|