1 /*
2 * Copyright (c) 2015, 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 package jdk.internal.util;
26
27 import jdk.internal.HotSpotIntrinsicCandidate;
28 import jdk.internal.misc.Unsafe;
29
30 /**
31 * Utility methods to work with arrays.
32 * This includes a set of methods to find a mismatch between two primitive arrays
33 * and a method to calculate the new size of an array to be reallocated
34 *
35 * <p>Array equality and lexicographical comparison can be built on top of
36 * array mismatch functionality.
37 *
38 * <p>The mismatch method implementation, {@link #vectorizedMismatch}, leverages
39 * vector-based techniques to access and compare the contents of two arrays.
40 * The Java implementation uses {@code Unsafe.getLongUnaligned} to access the
41 * content of an array, thus access is supported on platforms that do not
42 * support unaligned access. For a byte[] array, 8 bytes (64 bits) can be
43 * accessed and compared as a unit rather than individually, which increases
44 * the performance when the method is compiled by the HotSpot VM. On supported
45 * platforms the mismatch implementation is intrinsified to leverage SIMD
46 * instructions. So for a byte[] array, 16 bytes (128 bits), 32 bytes
47 * (256 bits), and perhaps in the future even 64 bytes (512 bits), platform
48 * permitting, can be accessed and compared as a unit, which further increases
49 * the performance over the Java implementation.
50 *
51 * <p>None of the mismatch methods perform array bounds checks. It is the
52 * responsibility of the caller (direct or otherwise) to perform such checks
53 * before calling this method.
54 */
55 public class ArraysSupport {
56 static final Unsafe U = Unsafe.getUnsafe();
57
58 private static final boolean BIG_ENDIAN = U.isBigEndian();
59
60 public static final int LOG2_ARRAY_BOOLEAN_INDEX_SCALE = exactLog2(Unsafe.ARRAY_BOOLEAN_INDEX_SCALE);
61 public static final int LOG2_ARRAY_BYTE_INDEX_SCALE = exactLog2(Unsafe.ARRAY_BYTE_INDEX_SCALE);
62 public static final int LOG2_ARRAY_CHAR_INDEX_SCALE = exactLog2(Unsafe.ARRAY_CHAR_INDEX_SCALE);
63 public static final int LOG2_ARRAY_SHORT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_SHORT_INDEX_SCALE);
64 public static final int LOG2_ARRAY_INT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_INT_INDEX_SCALE);
65 public static final int LOG2_ARRAY_LONG_INDEX_SCALE = exactLog2(Unsafe.ARRAY_LONG_INDEX_SCALE);
66 public static final int LOG2_ARRAY_FLOAT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_FLOAT_INDEX_SCALE);
67 public static final int LOG2_ARRAY_DOUBLE_INDEX_SCALE = exactLog2(Unsafe.ARRAY_DOUBLE_INDEX_SCALE);
68
69 private static final int LOG2_BYTE_BIT_SIZE = exactLog2(Byte.SIZE);
70
71 private static int exactLog2(int scale) {
72 if ((scale & (scale - 1)) != 0)
73 throw new Error("data type scale not a power of two");
74 return Integer.numberOfTrailingZeros(scale);
75 }
76
77 private ArraysSupport() {}
78
79 /**
80 * Find the relative index of the first mismatching pair of elements in two
81 * primitive arrays of the same component type. Pairs of elements will be
82 * tested in order relative to given offsets into both arrays.
83 *
84 * <p>This method does not perform type checks or bounds checks. It is the
85 * responsibility of the caller to perform such checks before calling this
86 * method.
87 *
88 * <p>The given offsets, in bytes, need not be aligned according to the
89 * given log<sub>2</sub> size the array elements. More specifically, an
90 * offset modulus the size need not be zero.
91 *
92 * @param a the first array to be tested for mismatch, or {@code null} for
93 * direct memory access
94 * @param aOffset the relative offset, in bytes, from the base address of
95 * the first array to test from, otherwise if the first array is
96 * {@code null}, an absolute address pointing to the first element to test.
97 * @param b the second array to be tested for mismatch, or {@code null} for
98 * direct memory access
99 * @param bOffset the relative offset, in bytes, from the base address of
100 * the second array to test from, otherwise if the second array is
101 * {@code null}, an absolute address pointing to the first element to test.
102 * @param length the number of array elements to test
103 * @param log2ArrayIndexScale log<sub>2</sub> of the array index scale, that
104 * corresponds to the size, in bytes, of an array element.
105 * @return if a mismatch is found a relative index, between 0 (inclusive)
106 * and {@code length} (exclusive), of the first mismatching pair of elements
107 * in the two arrays. Otherwise, if a mismatch is not found the bitwise
108 * compliment of the number of remaining pairs of elements to be checked in
109 * the tail of the two arrays.
110 */
111 @HotSpotIntrinsicCandidate
112 public static int vectorizedMismatch(Object a, long aOffset,
113 Object b, long bOffset,
114 int length,
115 int log2ArrayIndexScale) {
116 // assert a.getClass().isArray();
117 // assert b.getClass().isArray();
118 // assert 0 <= length <= sizeOf(a)
119 // assert 0 <= length <= sizeOf(b)
120 // assert 0 <= log2ArrayIndexScale <= 3
121
122 int log2ValuesPerWidth = LOG2_ARRAY_LONG_INDEX_SCALE - log2ArrayIndexScale;
123 int wi = 0;
124 for (; wi < length >> log2ValuesPerWidth; wi++) {
125 long bi = ((long) wi) << LOG2_ARRAY_LONG_INDEX_SCALE;
126 long av = U.getLongUnaligned(a, aOffset + bi);
127 long bv = U.getLongUnaligned(b, bOffset + bi);
128 if (av != bv) {
129 long x = av ^ bv;
130 int o = BIG_ENDIAN
131 ? Long.numberOfLeadingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale)
132 : Long.numberOfTrailingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale);
133 return (wi << log2ValuesPerWidth) + o;
134 }
135 }
136
137 // Calculate the tail of remaining elements to check
138 int tail = length - (wi << log2ValuesPerWidth);
139
140 if (log2ArrayIndexScale < LOG2_ARRAY_INT_INDEX_SCALE) {
141 int wordTail = 1 << (LOG2_ARRAY_INT_INDEX_SCALE - log2ArrayIndexScale);
142 // Handle 4 bytes or 2 chars in the tail using int width
143 if (tail >= wordTail) {
144 long bi = ((long) wi) << LOG2_ARRAY_LONG_INDEX_SCALE;
145 int av = U.getIntUnaligned(a, aOffset + bi);
146 int bv = U.getIntUnaligned(b, bOffset + bi);
147 if (av != bv) {
148 int x = av ^ bv;
149 int o = BIG_ENDIAN
150 ? Integer.numberOfLeadingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale)
151 : Integer.numberOfTrailingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale);
152 return (wi << log2ValuesPerWidth) + o;
153 }
154 tail -= wordTail;
155 }
156 return ~tail;
157 }
158 else {
159 return ~tail;
160 }
161 }
162
163 // Booleans
164 // Each boolean element takes up one byte
165
166 public static int mismatch(boolean[] a,
167 boolean[] b,
168 int length) {
169 int i = 0;
170 if (length > 7) {
171 if (a[0] != b[0])
172 return 0;
173 i = vectorizedMismatch(
174 a, Unsafe.ARRAY_BOOLEAN_BASE_OFFSET,
175 b, Unsafe.ARRAY_BOOLEAN_BASE_OFFSET,
176 length, LOG2_ARRAY_BOOLEAN_INDEX_SCALE);
177 if (i >= 0)
178 return i;
179 i = length - ~i;
180 }
181 for (; i < length; i++) {
182 if (a[i] != b[i])
183 return i;
184 }
185 return -1;
186 }
187
188 public static int mismatch(boolean[] a, int aFromIndex,
189 boolean[] b, int bFromIndex,
190 int length) {
191 int i = 0;
192 if (length > 7) {
193 if (a[aFromIndex] != b[bFromIndex])
194 return 0;
195 int aOffset = Unsafe.ARRAY_BOOLEAN_BASE_OFFSET + aFromIndex;
196 int bOffset = Unsafe.ARRAY_BOOLEAN_BASE_OFFSET + bFromIndex;
197 i = vectorizedMismatch(
198 a, aOffset,
199 b, bOffset,
200 length, LOG2_ARRAY_BOOLEAN_INDEX_SCALE);
201 if (i >= 0)
202 return i;
203 i = length - ~i;
204 }
205 for (; i < length; i++) {
206 if (a[aFromIndex + i] != b[bFromIndex + i])
207 return i;
208 }
209 return -1;
210 }
211
212
213 // Bytes
214
215 /**
216 * Find the index of a mismatch between two arrays.
217 *
218 * <p>This method does not perform bounds checks. It is the responsibility
219 * of the caller to perform such bounds checks before calling this method.
220 *
221 * @param a the first array to be tested for a mismatch
222 * @param b the second array to be tested for a mismatch
223 * @param length the number of bytes from each array to check
224 * @return the index of a mismatch between the two arrays, otherwise -1 if
225 * no mismatch. The index will be within the range of (inclusive) 0 to
226 * (exclusive) the smaller of the two array lengths.
227 */
228 public static int mismatch(byte[] a,
229 byte[] b,
230 int length) {
231 // ISSUE: defer to index receiving methods if performance is good
232 // assert length <= a.length
233 // assert length <= b.length
234
235 int i = 0;
236 if (length > 7) {
237 if (a[0] != b[0])
238 return 0;
239 i = vectorizedMismatch(
240 a, Unsafe.ARRAY_BYTE_BASE_OFFSET,
241 b, Unsafe.ARRAY_BYTE_BASE_OFFSET,
242 length, LOG2_ARRAY_BYTE_INDEX_SCALE);
243 if (i >= 0)
244 return i;
245 // Align to tail
246 i = length - ~i;
247 // assert i >= 0 && i <= 7;
248 }
249 // Tail < 8 bytes
250 for (; i < length; i++) {
251 if (a[i] != b[i])
252 return i;
253 }
254 return -1;
255 }
256
257 /**
258 * Find the relative index of a mismatch between two arrays starting from
259 * given indexes.
260 *
261 * <p>This method does not perform bounds checks. It is the responsibility
262 * of the caller to perform such bounds checks before calling this method.
263 *
264 * @param a the first array to be tested for a mismatch
265 * @param aFromIndex the index of the first element (inclusive) in the first
266 * array to be compared
267 * @param b the second array to be tested for a mismatch
268 * @param bFromIndex the index of the first element (inclusive) in the
269 * second array to be compared
270 * @param length the number of bytes from each array to check
271 * @return the relative index of a mismatch between the two arrays,
272 * otherwise -1 if no mismatch. The index will be within the range of
273 * (inclusive) 0 to (exclusive) the smaller of the two array bounds.
274 */
275 public static int mismatch(byte[] a, int aFromIndex,
276 byte[] b, int bFromIndex,
277 int length) {
278 // assert 0 <= aFromIndex < a.length
279 // assert 0 <= aFromIndex + length <= a.length
280 // assert 0 <= bFromIndex < b.length
281 // assert 0 <= bFromIndex + length <= b.length
282 // assert length >= 0
283
284 int i = 0;
285 if (length > 7) {
286 if (a[aFromIndex] != b[bFromIndex])
287 return 0;
288 int aOffset = Unsafe.ARRAY_BYTE_BASE_OFFSET + aFromIndex;
289 int bOffset = Unsafe.ARRAY_BYTE_BASE_OFFSET + bFromIndex;
290 i = vectorizedMismatch(
291 a, aOffset,
292 b, bOffset,
293 length, LOG2_ARRAY_BYTE_INDEX_SCALE);
294 if (i >= 0)
295 return i;
296 i = length - ~i;
297 }
298 for (; i < length; i++) {
299 if (a[aFromIndex + i] != b[bFromIndex + i])
300 return i;
301 }
302 return -1;
303 }
304
305
306 // Chars
307
308 public static int mismatch(char[] a,
309 char[] b,
310 int length) {
311 int i = 0;
312 if (length > 3) {
313 if (a[0] != b[0])
314 return 0;
315 i = vectorizedMismatch(
316 a, Unsafe.ARRAY_CHAR_BASE_OFFSET,
317 b, Unsafe.ARRAY_CHAR_BASE_OFFSET,
318 length, LOG2_ARRAY_CHAR_INDEX_SCALE);
319 if (i >= 0)
320 return i;
321 i = length - ~i;
322 }
323 for (; i < length; i++) {
324 if (a[i] != b[i])
325 return i;
326 }
327 return -1;
328 }
329
330 public static int mismatch(char[] a, int aFromIndex,
331 char[] b, int bFromIndex,
332 int length) {
333 int i = 0;
334 if (length > 3) {
335 if (a[aFromIndex] != b[bFromIndex])
336 return 0;
337 int aOffset = Unsafe.ARRAY_CHAR_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_CHAR_INDEX_SCALE);
338 int bOffset = Unsafe.ARRAY_CHAR_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_CHAR_INDEX_SCALE);
339 i = vectorizedMismatch(
340 a, aOffset,
341 b, bOffset,
342 length, LOG2_ARRAY_CHAR_INDEX_SCALE);
343 if (i >= 0)
344 return i;
345 i = length - ~i;
346 }
347 for (; i < length; i++) {
348 if (a[aFromIndex + i] != b[bFromIndex + i])
349 return i;
350 }
351 return -1;
352 }
353
354
355 // Shorts
356
357 public static int mismatch(short[] a,
358 short[] b,
359 int length) {
360 int i = 0;
361 if (length > 3) {
362 if (a[0] != b[0])
363 return 0;
364 i = vectorizedMismatch(
365 a, Unsafe.ARRAY_SHORT_BASE_OFFSET,
366 b, Unsafe.ARRAY_SHORT_BASE_OFFSET,
367 length, LOG2_ARRAY_SHORT_INDEX_SCALE);
368 if (i >= 0)
369 return i;
370 i = length - ~i;
371 }
372 for (; i < length; i++) {
373 if (a[i] != b[i])
374 return i;
375 }
376 return -1;
377 }
378
379 public static int mismatch(short[] a, int aFromIndex,
380 short[] b, int bFromIndex,
381 int length) {
382 int i = 0;
383 if (length > 3) {
384 if (a[aFromIndex] != b[bFromIndex])
385 return 0;
386 int aOffset = Unsafe.ARRAY_SHORT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_SHORT_INDEX_SCALE);
387 int bOffset = Unsafe.ARRAY_SHORT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_SHORT_INDEX_SCALE);
388 i = vectorizedMismatch(
389 a, aOffset,
390 b, bOffset,
391 length, LOG2_ARRAY_SHORT_INDEX_SCALE);
392 if (i >= 0)
393 return i;
394 i = length - ~i;
395 }
396 for (; i < length; i++) {
397 if (a[aFromIndex + i] != b[bFromIndex + i])
398 return i;
399 }
400 return -1;
401 }
402
403
404 // Ints
405
406 public static int mismatch(int[] a,
407 int[] b,
408 int length) {
409 int i = 0;
410 if (length > 1) {
411 if (a[0] != b[0])
412 return 0;
413 i = vectorizedMismatch(
414 a, Unsafe.ARRAY_INT_BASE_OFFSET,
415 b, Unsafe.ARRAY_INT_BASE_OFFSET,
416 length, LOG2_ARRAY_INT_INDEX_SCALE);
417 if (i >= 0)
418 return i;
419 i = length - ~i;
420 }
421 for (; i < length; i++) {
422 if (a[i] != b[i])
423 return i;
424 }
425 return -1;
426 }
427
428 public static int mismatch(int[] a, int aFromIndex,
429 int[] b, int bFromIndex,
430 int length) {
431 int i = 0;
432 if (length > 1) {
433 if (a[aFromIndex] != b[bFromIndex])
434 return 0;
435 int aOffset = Unsafe.ARRAY_INT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_INT_INDEX_SCALE);
436 int bOffset = Unsafe.ARRAY_INT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_INT_INDEX_SCALE);
437 i = vectorizedMismatch(
438 a, aOffset,
439 b, bOffset,
440 length, LOG2_ARRAY_INT_INDEX_SCALE);
441 if (i >= 0)
442 return i;
443 i = length - ~i;
444 }
445 for (; i < length; i++) {
446 if (a[aFromIndex + i] != b[bFromIndex + i])
447 return i;
448 }
449 return -1;
450 }
451
452
453 // Floats
454
455 public static int mismatch(float[] a,
456 float[] b,
457 int length) {
458 return mismatch(a, 0, b, 0, length);
459 }
460
461 public static int mismatch(float[] a, int aFromIndex,
462 float[] b, int bFromIndex,
463 int length) {
464 int i = 0;
465 if (length > 1) {
466 if (Float.floatToRawIntBits(a[aFromIndex]) == Float.floatToRawIntBits(b[bFromIndex])) {
467 int aOffset = Unsafe.ARRAY_FLOAT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_FLOAT_INDEX_SCALE);
468 int bOffset = Unsafe.ARRAY_FLOAT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_FLOAT_INDEX_SCALE);
469 i = vectorizedMismatch(
470 a, aOffset,
471 b, bOffset,
472 length, LOG2_ARRAY_FLOAT_INDEX_SCALE);
473 }
474 // Mismatched
475 if (i >= 0) {
476 // Check if mismatch is not associated with two NaN values
477 if (!Float.isNaN(a[aFromIndex + i]) || !Float.isNaN(b[bFromIndex + i]))
478 return i;
479
480 // Mismatch on two different NaN values that are normalized to match
481 // Fall back to slow mechanism
482 // ISSUE: Consider looping over vectorizedMismatch adjusting ranges
483 // However, requires that returned value be relative to input ranges
484 i++;
485 }
486 // Matched
487 else {
488 i = length - ~i;
489 }
490 }
491 for (; i < length; i++) {
492 if (Float.floatToIntBits(a[aFromIndex + i]) != Float.floatToIntBits(b[bFromIndex + i]))
493 return i;
494 }
495 return -1;
496 }
497
498 // 64 bit sizes
499
500 // Long
501
502 public static int mismatch(long[] a,
503 long[] b,
504 int length) {
505 if (length == 0) {
506 return -1;
507 }
508 if (a[0] != b[0])
509 return 0;
510 int i = vectorizedMismatch(
511 a, Unsafe.ARRAY_LONG_BASE_OFFSET,
512 b, Unsafe.ARRAY_LONG_BASE_OFFSET,
513 length, LOG2_ARRAY_LONG_INDEX_SCALE);
514 return i >= 0 ? i : -1;
515 }
516
517 public static int mismatch(long[] a, int aFromIndex,
518 long[] b, int bFromIndex,
519 int length) {
520 if (length == 0) {
521 return -1;
522 }
523 if (a[aFromIndex] != b[bFromIndex])
524 return 0;
525 int aOffset = Unsafe.ARRAY_LONG_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_LONG_INDEX_SCALE);
526 int bOffset = Unsafe.ARRAY_LONG_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_LONG_INDEX_SCALE);
527 int i = vectorizedMismatch(
528 a, aOffset,
529 b, bOffset,
530 length, LOG2_ARRAY_LONG_INDEX_SCALE);
531 return i >= 0 ? i : -1;
532 }
533
534
535 // Double
536
537 public static int mismatch(double[] a,
538 double[] b,
539 int length) {
540 return mismatch(a, 0, b, 0, length);
541 }
542
543 public static int mismatch(double[] a, int aFromIndex,
544 double[] b, int bFromIndex,
545 int length) {
546 if (length == 0) {
547 return -1;
548 }
549 int i = 0;
550 if (Double.doubleToRawLongBits(a[aFromIndex]) == Double.doubleToRawLongBits(b[bFromIndex])) {
551 int aOffset = Unsafe.ARRAY_DOUBLE_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_DOUBLE_INDEX_SCALE);
552 int bOffset = Unsafe.ARRAY_DOUBLE_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_DOUBLE_INDEX_SCALE);
553 i = vectorizedMismatch(
554 a, aOffset,
555 b, bOffset,
556 length, LOG2_ARRAY_DOUBLE_INDEX_SCALE);
557 }
558 if (i >= 0) {
559 // Check if mismatch is not associated with two NaN values
560 if (!Double.isNaN(a[aFromIndex + i]) || !Double.isNaN(b[bFromIndex + i]))
561 return i;
562
563 // Mismatch on two different NaN values that are normalized to match
564 // Fall back to slow mechanism
565 // ISSUE: Consider looping over vectorizedMismatch adjusting ranges
566 // However, requires that returned value be relative to input ranges
567 i++;
568 for (; i < length; i++) {
569 if (Double.doubleToLongBits(a[aFromIndex + i]) != Double.doubleToLongBits(b[bFromIndex + i]))
570 return i;
571 }
572 }
573
574 return -1;
575 }
576
577 /**
578 * The maximum size of array to allocate (unless necessary).
579 * Some VMs reserve some header words in an array.
580 * Attempts to allocate larger arrays may result in
581 * OutOfMemoryError: Requested array size exceeds VM limit
582 */
583 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
584
585 /**
586 * Calculates new size of an array to be reallocated.
587 *
588 * The result will be at least {@code oldCapacity + growAtLeastBy}.
589 * The result can be greater (normally, up to
590 * {@code oldCapacity + preferredGrowBy}).
591 * This function will not return values greater than
592 * {@link #MAX_ARRAY_SIZE} unless necessary.
593 *
594 * @param oldCapacity current size of the array
595 * @param growAtLeastBy minimum required growth of the array size
596 * @param preferredGrowBy preferred growth of the array size
597 * @return the new size of the array
598 * @throws OutOfMemoryError if increasing {@code oldCapacity) by
599 * {@code growAtLeastBy} overflows.
600 */
601 public static int newCapacity(int oldCapacity,
602 int growAtLeastBy,
603 int preferredGrowBy) {
604 assert oldCapacity >= 0;
605 assert growAtLeastBy > 0;
606
607 int newCapacity = oldCapacity + preferredGrowBy;
608 if (preferredGrowBy < growAtLeastBy) {
609 newCapacity = oldCapacity + growAtLeastBy;
610 }
611 return (newCapacity - MAX_ARRAY_SIZE > 0)
612 ? hugeCapacity(oldCapacity + growAtLeastBy) : newCapacity;
613 }
614
615 private static int hugeCapacity(int minCapacity) {
616 if (minCapacity < 0) { // overflow
617 throw new OutOfMemoryError("Required array size too large");
618 }
619 return (minCapacity > MAX_ARRAY_SIZE)
620 ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
621 }
622 }