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. This includes a set of methods
32 * to find a mismatch between two primitive arrays. Also included is
33 * a method to calculate the new length 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 /**
164 * Mismatch over long lengths.
165 */
166 public static long vectorizedMismatchLargeForBytes(Object a, long aOffset,
167 Object b, long bOffset,
168 long length) {
169 long off = 0;
170 long remaining = length;
171 int i, size;
172 boolean lastSubRange = false;
173 while (remaining > 7 && !lastSubRange) {
174 if (remaining > Integer.MAX_VALUE) {
175 size = Integer.MAX_VALUE;
176 } else {
177 size = (int) remaining;
178 lastSubRange = true;
179 }
180 i = vectorizedMismatch(
181 a, aOffset + off,
182 b, bOffset + off,
183 size, LOG2_ARRAY_BYTE_INDEX_SCALE);
184 if (i >= 0)
185 return off + i;
186
187 i = size - ~i;
188 off += i;
189 remaining -= i;
190 }
191 return ~remaining;
192 }
193
194 // Booleans
195 // Each boolean element takes up one byte
196
197 public static int mismatch(boolean[] a,
198 boolean[] b,
199 int length) {
200 int i = 0;
201 if (length > 7) {
202 if (a[0] != b[0])
203 return 0;
204 i = vectorizedMismatch(
205 a, Unsafe.ARRAY_BOOLEAN_BASE_OFFSET,
206 b, Unsafe.ARRAY_BOOLEAN_BASE_OFFSET,
207 length, LOG2_ARRAY_BOOLEAN_INDEX_SCALE);
208 if (i >= 0)
209 return i;
210 i = length - ~i;
211 }
212 for (; i < length; i++) {
213 if (a[i] != b[i])
214 return i;
215 }
216 return -1;
217 }
218
219 public static int mismatch(boolean[] a, int aFromIndex,
220 boolean[] b, int bFromIndex,
221 int length) {
222 int i = 0;
223 if (length > 7) {
224 if (a[aFromIndex] != b[bFromIndex])
225 return 0;
226 int aOffset = Unsafe.ARRAY_BOOLEAN_BASE_OFFSET + aFromIndex;
227 int bOffset = Unsafe.ARRAY_BOOLEAN_BASE_OFFSET + bFromIndex;
228 i = vectorizedMismatch(
229 a, aOffset,
230 b, bOffset,
231 length, LOG2_ARRAY_BOOLEAN_INDEX_SCALE);
232 if (i >= 0)
233 return i;
234 i = length - ~i;
235 }
236 for (; i < length; i++) {
237 if (a[aFromIndex + i] != b[bFromIndex + i])
238 return i;
239 }
240 return -1;
241 }
242
243
244 // Bytes
245
246 /**
247 * Find the index of a mismatch between two arrays.
248 *
249 * <p>This method does not perform bounds checks. It is the responsibility
250 * of the caller to perform such bounds checks before calling this method.
251 *
252 * @param a the first array to be tested for a mismatch
253 * @param b the second array to be tested for a mismatch
254 * @param length the number of bytes from each array to check
255 * @return the index of a mismatch between the two arrays, otherwise -1 if
256 * no mismatch. The index will be within the range of (inclusive) 0 to
257 * (exclusive) the smaller of the two array lengths.
258 */
259 public static int mismatch(byte[] a,
260 byte[] b,
261 int length) {
262 // ISSUE: defer to index receiving methods if performance is good
263 // assert length <= a.length
264 // assert length <= b.length
265
266 int i = 0;
267 if (length > 7) {
268 if (a[0] != b[0])
269 return 0;
270 i = vectorizedMismatch(
271 a, Unsafe.ARRAY_BYTE_BASE_OFFSET,
272 b, Unsafe.ARRAY_BYTE_BASE_OFFSET,
273 length, LOG2_ARRAY_BYTE_INDEX_SCALE);
274 if (i >= 0)
275 return i;
276 // Align to tail
277 i = length - ~i;
278 // assert i >= 0 && i <= 7;
279 }
280 // Tail < 8 bytes
281 for (; i < length; i++) {
282 if (a[i] != b[i])
283 return i;
284 }
285 return -1;
286 }
287
288 /**
289 * Find the relative index of a mismatch between two arrays starting from
290 * given indexes.
291 *
292 * <p>This method does not perform bounds checks. It is the responsibility
293 * of the caller to perform such bounds checks before calling this method.
294 *
295 * @param a the first array to be tested for a mismatch
296 * @param aFromIndex the index of the first element (inclusive) in the first
297 * array to be compared
298 * @param b the second array to be tested for a mismatch
299 * @param bFromIndex the index of the first element (inclusive) in the
300 * second array to be compared
301 * @param length the number of bytes from each array to check
302 * @return the relative index of a mismatch between the two arrays,
303 * otherwise -1 if no mismatch. The index will be within the range of
304 * (inclusive) 0 to (exclusive) the smaller of the two array bounds.
305 */
306 public static int mismatch(byte[] a, int aFromIndex,
307 byte[] b, int bFromIndex,
308 int length) {
309 // assert 0 <= aFromIndex < a.length
310 // assert 0 <= aFromIndex + length <= a.length
311 // assert 0 <= bFromIndex < b.length
312 // assert 0 <= bFromIndex + length <= b.length
313 // assert length >= 0
314
315 int i = 0;
316 if (length > 7) {
317 if (a[aFromIndex] != b[bFromIndex])
318 return 0;
319 int aOffset = Unsafe.ARRAY_BYTE_BASE_OFFSET + aFromIndex;
320 int bOffset = Unsafe.ARRAY_BYTE_BASE_OFFSET + bFromIndex;
321 i = vectorizedMismatch(
322 a, aOffset,
323 b, bOffset,
324 length, LOG2_ARRAY_BYTE_INDEX_SCALE);
325 if (i >= 0)
326 return i;
327 i = length - ~i;
328 }
329 for (; i < length; i++) {
330 if (a[aFromIndex + i] != b[bFromIndex + i])
331 return i;
332 }
333 return -1;
334 }
335
336
337 // Chars
338
339 public static int mismatch(char[] a,
340 char[] b,
341 int length) {
342 int i = 0;
343 if (length > 3) {
344 if (a[0] != b[0])
345 return 0;
346 i = vectorizedMismatch(
347 a, Unsafe.ARRAY_CHAR_BASE_OFFSET,
348 b, Unsafe.ARRAY_CHAR_BASE_OFFSET,
349 length, LOG2_ARRAY_CHAR_INDEX_SCALE);
350 if (i >= 0)
351 return i;
352 i = length - ~i;
353 }
354 for (; i < length; i++) {
355 if (a[i] != b[i])
356 return i;
357 }
358 return -1;
359 }
360
361 public static int mismatch(char[] a, int aFromIndex,
362 char[] b, int bFromIndex,
363 int length) {
364 int i = 0;
365 if (length > 3) {
366 if (a[aFromIndex] != b[bFromIndex])
367 return 0;
368 int aOffset = Unsafe.ARRAY_CHAR_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_CHAR_INDEX_SCALE);
369 int bOffset = Unsafe.ARRAY_CHAR_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_CHAR_INDEX_SCALE);
370 i = vectorizedMismatch(
371 a, aOffset,
372 b, bOffset,
373 length, LOG2_ARRAY_CHAR_INDEX_SCALE);
374 if (i >= 0)
375 return i;
376 i = length - ~i;
377 }
378 for (; i < length; i++) {
379 if (a[aFromIndex + i] != b[bFromIndex + i])
380 return i;
381 }
382 return -1;
383 }
384
385
386 // Shorts
387
388 public static int mismatch(short[] a,
389 short[] b,
390 int length) {
391 int i = 0;
392 if (length > 3) {
393 if (a[0] != b[0])
394 return 0;
395 i = vectorizedMismatch(
396 a, Unsafe.ARRAY_SHORT_BASE_OFFSET,
397 b, Unsafe.ARRAY_SHORT_BASE_OFFSET,
398 length, LOG2_ARRAY_SHORT_INDEX_SCALE);
399 if (i >= 0)
400 return i;
401 i = length - ~i;
402 }
403 for (; i < length; i++) {
404 if (a[i] != b[i])
405 return i;
406 }
407 return -1;
408 }
409
410 public static int mismatch(short[] a, int aFromIndex,
411 short[] b, int bFromIndex,
412 int length) {
413 int i = 0;
414 if (length > 3) {
415 if (a[aFromIndex] != b[bFromIndex])
416 return 0;
417 int aOffset = Unsafe.ARRAY_SHORT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_SHORT_INDEX_SCALE);
418 int bOffset = Unsafe.ARRAY_SHORT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_SHORT_INDEX_SCALE);
419 i = vectorizedMismatch(
420 a, aOffset,
421 b, bOffset,
422 length, LOG2_ARRAY_SHORT_INDEX_SCALE);
423 if (i >= 0)
424 return i;
425 i = length - ~i;
426 }
427 for (; i < length; i++) {
428 if (a[aFromIndex + i] != b[bFromIndex + i])
429 return i;
430 }
431 return -1;
432 }
433
434
435 // Ints
436
437 public static int mismatch(int[] a,
438 int[] b,
439 int length) {
440 int i = 0;
441 if (length > 1) {
442 if (a[0] != b[0])
443 return 0;
444 i = vectorizedMismatch(
445 a, Unsafe.ARRAY_INT_BASE_OFFSET,
446 b, Unsafe.ARRAY_INT_BASE_OFFSET,
447 length, LOG2_ARRAY_INT_INDEX_SCALE);
448 if (i >= 0)
449 return i;
450 i = length - ~i;
451 }
452 for (; i < length; i++) {
453 if (a[i] != b[i])
454 return i;
455 }
456 return -1;
457 }
458
459 public static int mismatch(int[] a, int aFromIndex,
460 int[] b, int bFromIndex,
461 int length) {
462 int i = 0;
463 if (length > 1) {
464 if (a[aFromIndex] != b[bFromIndex])
465 return 0;
466 int aOffset = Unsafe.ARRAY_INT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_INT_INDEX_SCALE);
467 int bOffset = Unsafe.ARRAY_INT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_INT_INDEX_SCALE);
468 i = vectorizedMismatch(
469 a, aOffset,
470 b, bOffset,
471 length, LOG2_ARRAY_INT_INDEX_SCALE);
472 if (i >= 0)
473 return i;
474 i = length - ~i;
475 }
476 for (; i < length; i++) {
477 if (a[aFromIndex + i] != b[bFromIndex + i])
478 return i;
479 }
480 return -1;
481 }
482
483
484 // Floats
485
486 public static int mismatch(float[] a,
487 float[] b,
488 int length) {
489 return mismatch(a, 0, b, 0, length);
490 }
491
492 public static int mismatch(float[] a, int aFromIndex,
493 float[] b, int bFromIndex,
494 int length) {
495 int i = 0;
496 if (length > 1) {
497 if (Float.floatToRawIntBits(a[aFromIndex]) == Float.floatToRawIntBits(b[bFromIndex])) {
498 int aOffset = Unsafe.ARRAY_FLOAT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_FLOAT_INDEX_SCALE);
499 int bOffset = Unsafe.ARRAY_FLOAT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_FLOAT_INDEX_SCALE);
500 i = vectorizedMismatch(
501 a, aOffset,
502 b, bOffset,
503 length, LOG2_ARRAY_FLOAT_INDEX_SCALE);
504 }
505 // Mismatched
506 if (i >= 0) {
507 // Check if mismatch is not associated with two NaN values
508 if (!Float.isNaN(a[aFromIndex + i]) || !Float.isNaN(b[bFromIndex + i]))
509 return i;
510
511 // Mismatch on two different NaN values that are normalized to match
512 // Fall back to slow mechanism
513 // ISSUE: Consider looping over vectorizedMismatch adjusting ranges
514 // However, requires that returned value be relative to input ranges
515 i++;
516 }
517 // Matched
518 else {
519 i = length - ~i;
520 }
521 }
522 for (; i < length; i++) {
523 if (Float.floatToIntBits(a[aFromIndex + i]) != Float.floatToIntBits(b[bFromIndex + i]))
524 return i;
525 }
526 return -1;
527 }
528
529 // 64 bit sizes
530
531 // Long
532
533 public static int mismatch(long[] a,
534 long[] b,
535 int length) {
536 if (length == 0) {
537 return -1;
538 }
539 if (a[0] != b[0])
540 return 0;
541 int i = vectorizedMismatch(
542 a, Unsafe.ARRAY_LONG_BASE_OFFSET,
543 b, Unsafe.ARRAY_LONG_BASE_OFFSET,
544 length, LOG2_ARRAY_LONG_INDEX_SCALE);
545 return i >= 0 ? i : -1;
546 }
547
548 public static int mismatch(long[] a, int aFromIndex,
549 long[] b, int bFromIndex,
550 int length) {
551 if (length == 0) {
552 return -1;
553 }
554 if (a[aFromIndex] != b[bFromIndex])
555 return 0;
556 int aOffset = Unsafe.ARRAY_LONG_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_LONG_INDEX_SCALE);
557 int bOffset = Unsafe.ARRAY_LONG_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_LONG_INDEX_SCALE);
558 int i = vectorizedMismatch(
559 a, aOffset,
560 b, bOffset,
561 length, LOG2_ARRAY_LONG_INDEX_SCALE);
562 return i >= 0 ? i : -1;
563 }
564
565
566 // Double
567
568 public static int mismatch(double[] a,
569 double[] b,
570 int length) {
571 return mismatch(a, 0, b, 0, length);
572 }
573
574 public static int mismatch(double[] a, int aFromIndex,
575 double[] b, int bFromIndex,
576 int length) {
577 if (length == 0) {
578 return -1;
579 }
580 int i = 0;
581 if (Double.doubleToRawLongBits(a[aFromIndex]) == Double.doubleToRawLongBits(b[bFromIndex])) {
582 int aOffset = Unsafe.ARRAY_DOUBLE_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_DOUBLE_INDEX_SCALE);
583 int bOffset = Unsafe.ARRAY_DOUBLE_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_DOUBLE_INDEX_SCALE);
584 i = vectorizedMismatch(
585 a, aOffset,
586 b, bOffset,
587 length, LOG2_ARRAY_DOUBLE_INDEX_SCALE);
588 }
589 if (i >= 0) {
590 // Check if mismatch is not associated with two NaN values
591 if (!Double.isNaN(a[aFromIndex + i]) || !Double.isNaN(b[bFromIndex + i]))
592 return i;
593
594 // Mismatch on two different NaN values that are normalized to match
595 // Fall back to slow mechanism
596 // ISSUE: Consider looping over vectorizedMismatch adjusting ranges
597 // However, requires that returned value be relative to input ranges
598 i++;
599 for (; i < length; i++) {
600 if (Double.doubleToLongBits(a[aFromIndex + i]) != Double.doubleToLongBits(b[bFromIndex + i]))
601 return i;
602 }
603 }
604
605 return -1;
606 }
607
608 /**
609 * The maximum length of array to allocate (unless necessary).
610 * Some VMs reserve some header words in an array.
611 * Attempts to allocate larger arrays may result in
612 * {@code OutOfMemoryError: Requested array size exceeds VM limit}
613 */
614 public static final int MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;
615
616 /**
617 * Calculates a new array length given an array's current length, a preferred
618 * growth value, and a minimum growth value. If the preferred growth value
619 * is less than the minimum growth value, the minimum growth value is used in
620 * its place. If the sum of the current length and the preferred growth
621 * value does not exceed {@link #MAX_ARRAY_LENGTH}, that sum is returned.
622 * If the sum of the current length and the minimum growth value does not
623 * exceed {@code MAX_ARRAY_LENGTH}, then {@code MAX_ARRAY_LENGTH} is returned.
624 * If the sum does not overflow an int, then {@code Integer.MAX_VALUE} is
625 * returned. Otherwise, {@code OutOfMemoryError} is thrown.
626 *
627 * @param oldLength current length of the array (must be non negative)
628 * @param minGrowth minimum required growth of the array length (must be
629 * positive)
630 * @param prefGrowth preferred growth of the array length (ignored, if less
631 * then {@code minGrowth})
632 * @return the new length of the array
633 * @throws OutOfMemoryError if increasing {@code oldLength} by
634 * {@code minGrowth} overflows.
635 */
636 public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
637 // assert oldLength >= 0
638 // assert minGrowth > 0
639
640 int newLength = Math.max(minGrowth, prefGrowth) + oldLength;
641 if (newLength - MAX_ARRAY_LENGTH <= 0) {
642 return newLength;
643 }
644 return hugeLength(oldLength, minGrowth);
645 }
646
647 private static int hugeLength(int oldLength, int minGrowth) {
648 int minLength = oldLength + minGrowth;
649 if (minLength < 0) { // overflow
650 throw new OutOfMemoryError("Required array length too large");
651 }
652 if (minLength <= MAX_ARRAY_LENGTH) {
653 return MAX_ARRAY_LENGTH;
654 }
655 return Integer.MAX_VALUE;
656 }
657 }