1 /* 2 * Copyright (c) 2015, 2021, 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.misc.Unsafe; 28 import jdk.internal.vm.annotation.IntrinsicCandidate; 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 // Android-changed: Android is little endian. 59 private static final boolean BIG_ENDIAN = false; 60 61 public static final int LOG2_ARRAY_BOOLEAN_INDEX_SCALE = exactLog2(Unsafe.ARRAY_BOOLEAN_INDEX_SCALE); 62 public static final int LOG2_ARRAY_BYTE_INDEX_SCALE = exactLog2(Unsafe.ARRAY_BYTE_INDEX_SCALE); 63 public static final int LOG2_ARRAY_CHAR_INDEX_SCALE = exactLog2(Unsafe.ARRAY_CHAR_INDEX_SCALE); 64 public static final int LOG2_ARRAY_SHORT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_SHORT_INDEX_SCALE); 65 public static final int LOG2_ARRAY_INT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_INT_INDEX_SCALE); 66 public static final int LOG2_ARRAY_LONG_INDEX_SCALE = exactLog2(Unsafe.ARRAY_LONG_INDEX_SCALE); 67 public static final int LOG2_ARRAY_FLOAT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_FLOAT_INDEX_SCALE); 68 public static final int LOG2_ARRAY_DOUBLE_INDEX_SCALE = exactLog2(Unsafe.ARRAY_DOUBLE_INDEX_SCALE); 69 70 private static final int LOG2_BYTE_BIT_SIZE = exactLog2(Byte.SIZE); 71 exactLog2(int scale)72 private static int exactLog2(int scale) { 73 if ((scale & (scale - 1)) != 0) 74 throw new Error("data type scale not a power of two"); 75 return Integer.numberOfTrailingZeros(scale); 76 } 77 ArraysSupport()78 private ArraysSupport() {} 79 80 /** 81 * Find the relative index of the first mismatching pair of elements in two 82 * primitive arrays of the same component type. Pairs of elements will be 83 * tested in order relative to given offsets into both arrays. 84 * 85 * <p>This method does not perform type checks or bounds checks. It is the 86 * responsibility of the caller to perform such checks before calling this 87 * method. 88 * 89 * <p>The given offsets, in bytes, need not be aligned according to the 90 * given log<sub>2</sub> size the array elements. More specifically, an 91 * offset modulus the size need not be zero. 92 * 93 * @param a the first array to be tested for mismatch, or {@code null} for 94 * direct memory access 95 * @param aOffset the relative offset, in bytes, from the base address of 96 * the first array to test from, otherwise if the first array is 97 * {@code null}, an absolute address pointing to the first element to test. 98 * @param b the second array to be tested for mismatch, or {@code null} for 99 * direct memory access 100 * @param bOffset the relative offset, in bytes, from the base address of 101 * the second array to test from, otherwise if the second array is 102 * {@code null}, an absolute address pointing to the first element to test. 103 * @param length the number of array elements to test 104 * @param log2ArrayIndexScale log<sub>2</sub> of the array index scale, that 105 * corresponds to the size, in bytes, of an array element. 106 * @return if a mismatch is found a relative index, between 0 (inclusive) 107 * and {@code length} (exclusive), of the first mismatching pair of elements 108 * in the two arrays. Otherwise, if a mismatch is not found the bitwise 109 * compliment of the number of remaining pairs of elements to be checked in 110 * the tail of the two arrays. 111 */ 112 @IntrinsicCandidate vectorizedMismatch(Object a, long aOffset, Object b, long bOffset, int length, int log2ArrayIndexScale)113 public static int vectorizedMismatch(Object a, long aOffset, 114 Object b, long bOffset, 115 int length, 116 int log2ArrayIndexScale) { 117 // assert a.getClass().isArray(); 118 // assert b.getClass().isArray(); 119 // assert 0 <= length <= sizeOf(a) 120 // assert 0 <= length <= sizeOf(b) 121 // assert 0 <= log2ArrayIndexScale <= 3 122 123 int log2ValuesPerWidth = LOG2_ARRAY_LONG_INDEX_SCALE - log2ArrayIndexScale; 124 int wi = 0; 125 for (; wi < length >> log2ValuesPerWidth; wi++) { 126 long bi = ((long) wi) << LOG2_ARRAY_LONG_INDEX_SCALE; 127 long av = U.getLongUnaligned(a, aOffset + bi); 128 long bv = U.getLongUnaligned(b, bOffset + bi); 129 if (av != bv) { 130 long x = av ^ bv; 131 int o = BIG_ENDIAN 132 ? Long.numberOfLeadingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale) 133 : Long.numberOfTrailingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale); 134 return (wi << log2ValuesPerWidth) + o; 135 } 136 } 137 138 // Calculate the tail of remaining elements to check 139 int tail = length - (wi << log2ValuesPerWidth); 140 141 if (log2ArrayIndexScale < LOG2_ARRAY_INT_INDEX_SCALE) { 142 int wordTail = 1 << (LOG2_ARRAY_INT_INDEX_SCALE - log2ArrayIndexScale); 143 // Handle 4 bytes or 2 chars in the tail using int width 144 if (tail >= wordTail) { 145 long bi = ((long) wi) << LOG2_ARRAY_LONG_INDEX_SCALE; 146 int av = U.getIntUnaligned(a, aOffset + bi); 147 int bv = U.getIntUnaligned(b, bOffset + bi); 148 if (av != bv) { 149 int x = av ^ bv; 150 int o = BIG_ENDIAN 151 ? Integer.numberOfLeadingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale) 152 : Integer.numberOfTrailingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale); 153 return (wi << log2ValuesPerWidth) + o; 154 } 155 tail -= wordTail; 156 } 157 return ~tail; 158 } 159 else { 160 return ~tail; 161 } 162 } 163 164 // Booleans 165 // Each boolean element takes up one byte 166 mismatch(boolean[] a, boolean[] b, int length)167 public static int mismatch(boolean[] a, 168 boolean[] b, 169 int length) { 170 int i = 0; 171 if (length > 7) { 172 if (a[0] != b[0]) 173 return 0; 174 i = vectorizedMismatch( 175 a, Unsafe.ARRAY_BOOLEAN_BASE_OFFSET, 176 b, Unsafe.ARRAY_BOOLEAN_BASE_OFFSET, 177 length, LOG2_ARRAY_BOOLEAN_INDEX_SCALE); 178 if (i >= 0) 179 return i; 180 i = length - ~i; 181 } 182 for (; i < length; i++) { 183 if (a[i] != b[i]) 184 return i; 185 } 186 return -1; 187 } 188 mismatch(boolean[] a, int aFromIndex, boolean[] b, int bFromIndex, int length)189 public static int mismatch(boolean[] a, int aFromIndex, 190 boolean[] b, int bFromIndex, 191 int length) { 192 int i = 0; 193 if (length > 7) { 194 if (a[aFromIndex] != b[bFromIndex]) 195 return 0; 196 int aOffset = Unsafe.ARRAY_BOOLEAN_BASE_OFFSET + aFromIndex; 197 int bOffset = Unsafe.ARRAY_BOOLEAN_BASE_OFFSET + bFromIndex; 198 i = vectorizedMismatch( 199 a, aOffset, 200 b, bOffset, 201 length, LOG2_ARRAY_BOOLEAN_INDEX_SCALE); 202 if (i >= 0) 203 return i; 204 i = length - ~i; 205 } 206 for (; i < length; i++) { 207 if (a[aFromIndex + i] != b[bFromIndex + i]) 208 return i; 209 } 210 return -1; 211 } 212 213 214 // Bytes 215 216 /** 217 * Find the index of a mismatch between two arrays. 218 * 219 * <p>This method does not perform bounds checks. It is the responsibility 220 * of the caller to perform such bounds checks before calling this method. 221 * 222 * @param a the first array to be tested for a mismatch 223 * @param b the second array to be tested for a mismatch 224 * @param length the number of bytes from each array to check 225 * @return the index of a mismatch between the two arrays, otherwise -1 if 226 * no mismatch. The index will be within the range of (inclusive) 0 to 227 * (exclusive) the smaller of the two array lengths. 228 */ mismatch(byte[] a, byte[] b, int length)229 public static int mismatch(byte[] a, 230 byte[] b, 231 int length) { 232 // ISSUE: defer to index receiving methods if performance is good 233 // assert length <= a.length 234 // assert length <= b.length 235 236 int i = 0; 237 if (length > 7) { 238 if (a[0] != b[0]) 239 return 0; 240 i = vectorizedMismatch( 241 a, Unsafe.ARRAY_BYTE_BASE_OFFSET, 242 b, Unsafe.ARRAY_BYTE_BASE_OFFSET, 243 length, LOG2_ARRAY_BYTE_INDEX_SCALE); 244 if (i >= 0) 245 return i; 246 // Align to tail 247 i = length - ~i; 248 // assert i >= 0 && i <= 7; 249 } 250 // Tail < 8 bytes 251 for (; i < length; i++) { 252 if (a[i] != b[i]) 253 return i; 254 } 255 return -1; 256 } 257 258 /** 259 * Find the relative index of a mismatch between two arrays starting from 260 * given indexes. 261 * 262 * <p>This method does not perform bounds checks. It is the responsibility 263 * of the caller to perform such bounds checks before calling this method. 264 * 265 * @param a the first array to be tested for a mismatch 266 * @param aFromIndex the index of the first element (inclusive) in the first 267 * array to be compared 268 * @param b the second array to be tested for a mismatch 269 * @param bFromIndex the index of the first element (inclusive) in the 270 * second array to be compared 271 * @param length the number of bytes from each array to check 272 * @return the relative index of a mismatch between the two arrays, 273 * otherwise -1 if no mismatch. The index will be within the range of 274 * (inclusive) 0 to (exclusive) the smaller of the two array bounds. 275 */ mismatch(byte[] a, int aFromIndex, byte[] b, int bFromIndex, int length)276 public static int mismatch(byte[] a, int aFromIndex, 277 byte[] b, int bFromIndex, 278 int length) { 279 // assert 0 <= aFromIndex < a.length 280 // assert 0 <= aFromIndex + length <= a.length 281 // assert 0 <= bFromIndex < b.length 282 // assert 0 <= bFromIndex + length <= b.length 283 // assert length >= 0 284 285 int i = 0; 286 if (length > 7) { 287 if (a[aFromIndex] != b[bFromIndex]) 288 return 0; 289 int aOffset = Unsafe.ARRAY_BYTE_BASE_OFFSET + aFromIndex; 290 int bOffset = Unsafe.ARRAY_BYTE_BASE_OFFSET + bFromIndex; 291 i = vectorizedMismatch( 292 a, aOffset, 293 b, bOffset, 294 length, LOG2_ARRAY_BYTE_INDEX_SCALE); 295 if (i >= 0) 296 return i; 297 i = length - ~i; 298 } 299 for (; i < length; i++) { 300 if (a[aFromIndex + i] != b[bFromIndex + i]) 301 return i; 302 } 303 return -1; 304 } 305 306 307 // Chars 308 mismatch(char[] a, char[] b, int length)309 public static int mismatch(char[] a, 310 char[] b, 311 int length) { 312 int i = 0; 313 if (length > 3) { 314 if (a[0] != b[0]) 315 return 0; 316 i = vectorizedMismatch( 317 a, Unsafe.ARRAY_CHAR_BASE_OFFSET, 318 b, Unsafe.ARRAY_CHAR_BASE_OFFSET, 319 length, LOG2_ARRAY_CHAR_INDEX_SCALE); 320 if (i >= 0) 321 return i; 322 i = length - ~i; 323 } 324 for (; i < length; i++) { 325 if (a[i] != b[i]) 326 return i; 327 } 328 return -1; 329 } 330 mismatch(char[] a, int aFromIndex, char[] b, int bFromIndex, int length)331 public static int mismatch(char[] a, int aFromIndex, 332 char[] b, int bFromIndex, 333 int length) { 334 int i = 0; 335 if (length > 3) { 336 if (a[aFromIndex] != b[bFromIndex]) 337 return 0; 338 int aOffset = Unsafe.ARRAY_CHAR_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_CHAR_INDEX_SCALE); 339 int bOffset = Unsafe.ARRAY_CHAR_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_CHAR_INDEX_SCALE); 340 i = vectorizedMismatch( 341 a, aOffset, 342 b, bOffset, 343 length, LOG2_ARRAY_CHAR_INDEX_SCALE); 344 if (i >= 0) 345 return i; 346 i = length - ~i; 347 } 348 for (; i < length; i++) { 349 if (a[aFromIndex + i] != b[bFromIndex + i]) 350 return i; 351 } 352 return -1; 353 } 354 355 356 // Shorts 357 mismatch(short[] a, short[] b, int length)358 public static int mismatch(short[] a, 359 short[] b, 360 int length) { 361 int i = 0; 362 if (length > 3) { 363 if (a[0] != b[0]) 364 return 0; 365 i = vectorizedMismatch( 366 a, Unsafe.ARRAY_SHORT_BASE_OFFSET, 367 b, Unsafe.ARRAY_SHORT_BASE_OFFSET, 368 length, LOG2_ARRAY_SHORT_INDEX_SCALE); 369 if (i >= 0) 370 return i; 371 i = length - ~i; 372 } 373 for (; i < length; i++) { 374 if (a[i] != b[i]) 375 return i; 376 } 377 return -1; 378 } 379 mismatch(short[] a, int aFromIndex, short[] b, int bFromIndex, int length)380 public static int mismatch(short[] a, int aFromIndex, 381 short[] b, int bFromIndex, 382 int length) { 383 int i = 0; 384 if (length > 3) { 385 if (a[aFromIndex] != b[bFromIndex]) 386 return 0; 387 int aOffset = Unsafe.ARRAY_SHORT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_SHORT_INDEX_SCALE); 388 int bOffset = Unsafe.ARRAY_SHORT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_SHORT_INDEX_SCALE); 389 i = vectorizedMismatch( 390 a, aOffset, 391 b, bOffset, 392 length, LOG2_ARRAY_SHORT_INDEX_SCALE); 393 if (i >= 0) 394 return i; 395 i = length - ~i; 396 } 397 for (; i < length; i++) { 398 if (a[aFromIndex + i] != b[bFromIndex + i]) 399 return i; 400 } 401 return -1; 402 } 403 404 405 // Ints 406 mismatch(int[] a, int[] b, int length)407 public static int mismatch(int[] a, 408 int[] b, 409 int length) { 410 int i = 0; 411 if (length > 1) { 412 if (a[0] != b[0]) 413 return 0; 414 i = vectorizedMismatch( 415 a, Unsafe.ARRAY_INT_BASE_OFFSET, 416 b, Unsafe.ARRAY_INT_BASE_OFFSET, 417 length, LOG2_ARRAY_INT_INDEX_SCALE); 418 if (i >= 0) 419 return i; 420 i = length - ~i; 421 } 422 for (; i < length; i++) { 423 if (a[i] != b[i]) 424 return i; 425 } 426 return -1; 427 } 428 mismatch(int[] a, int aFromIndex, int[] b, int bFromIndex, int length)429 public static int mismatch(int[] a, int aFromIndex, 430 int[] b, int bFromIndex, 431 int length) { 432 int i = 0; 433 if (length > 1) { 434 if (a[aFromIndex] != b[bFromIndex]) 435 return 0; 436 int aOffset = Unsafe.ARRAY_INT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_INT_INDEX_SCALE); 437 int bOffset = Unsafe.ARRAY_INT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_INT_INDEX_SCALE); 438 i = vectorizedMismatch( 439 a, aOffset, 440 b, bOffset, 441 length, LOG2_ARRAY_INT_INDEX_SCALE); 442 if (i >= 0) 443 return i; 444 i = length - ~i; 445 } 446 for (; i < length; i++) { 447 if (a[aFromIndex + i] != b[bFromIndex + i]) 448 return i; 449 } 450 return -1; 451 } 452 453 454 // Floats 455 mismatch(float[] a, float[] b, int length)456 public static int mismatch(float[] a, 457 float[] b, 458 int length) { 459 return mismatch(a, 0, b, 0, length); 460 } 461 mismatch(float[] a, int aFromIndex, float[] b, int bFromIndex, int length)462 public static int mismatch(float[] a, int aFromIndex, 463 float[] b, int bFromIndex, 464 int length) { 465 int i = 0; 466 if (length > 1) { 467 if (Float.floatToRawIntBits(a[aFromIndex]) == Float.floatToRawIntBits(b[bFromIndex])) { 468 int aOffset = Unsafe.ARRAY_FLOAT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_FLOAT_INDEX_SCALE); 469 int bOffset = Unsafe.ARRAY_FLOAT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_FLOAT_INDEX_SCALE); 470 i = vectorizedMismatch( 471 a, aOffset, 472 b, bOffset, 473 length, LOG2_ARRAY_FLOAT_INDEX_SCALE); 474 } 475 // Mismatched 476 if (i >= 0) { 477 // Check if mismatch is not associated with two NaN values 478 if (!Float.isNaN(a[aFromIndex + i]) || !Float.isNaN(b[bFromIndex + i])) 479 return i; 480 481 // Mismatch on two different NaN values that are normalized to match 482 // Fall back to slow mechanism 483 // ISSUE: Consider looping over vectorizedMismatch adjusting ranges 484 // However, requires that returned value be relative to input ranges 485 i++; 486 } 487 // Matched 488 else { 489 i = length - ~i; 490 } 491 } 492 for (; i < length; i++) { 493 if (Float.floatToIntBits(a[aFromIndex + i]) != Float.floatToIntBits(b[bFromIndex + i])) 494 return i; 495 } 496 return -1; 497 } 498 499 // 64 bit sizes 500 501 // Long 502 mismatch(long[] a, long[] b, int length)503 public static int mismatch(long[] a, 504 long[] b, 505 int length) { 506 if (length == 0) { 507 return -1; 508 } 509 if (a[0] != b[0]) 510 return 0; 511 int i = vectorizedMismatch( 512 a, Unsafe.ARRAY_LONG_BASE_OFFSET, 513 b, Unsafe.ARRAY_LONG_BASE_OFFSET, 514 length, LOG2_ARRAY_LONG_INDEX_SCALE); 515 return i >= 0 ? i : -1; 516 } 517 mismatch(long[] a, int aFromIndex, long[] b, int bFromIndex, int length)518 public static int mismatch(long[] a, int aFromIndex, 519 long[] b, int bFromIndex, 520 int length) { 521 if (length == 0) { 522 return -1; 523 } 524 if (a[aFromIndex] != b[bFromIndex]) 525 return 0; 526 int aOffset = Unsafe.ARRAY_LONG_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_LONG_INDEX_SCALE); 527 int bOffset = Unsafe.ARRAY_LONG_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_LONG_INDEX_SCALE); 528 int i = vectorizedMismatch( 529 a, aOffset, 530 b, bOffset, 531 length, LOG2_ARRAY_LONG_INDEX_SCALE); 532 return i >= 0 ? i : -1; 533 } 534 535 536 // Double 537 mismatch(double[] a, double[] b, int length)538 public static int mismatch(double[] a, 539 double[] b, 540 int length) { 541 return mismatch(a, 0, b, 0, length); 542 } 543 mismatch(double[] a, int aFromIndex, double[] b, int bFromIndex, int length)544 public static int mismatch(double[] a, int aFromIndex, 545 double[] b, int bFromIndex, 546 int length) { 547 if (length == 0) { 548 return -1; 549 } 550 int i = 0; 551 if (Double.doubleToRawLongBits(a[aFromIndex]) == Double.doubleToRawLongBits(b[bFromIndex])) { 552 int aOffset = Unsafe.ARRAY_DOUBLE_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_DOUBLE_INDEX_SCALE); 553 int bOffset = Unsafe.ARRAY_DOUBLE_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_DOUBLE_INDEX_SCALE); 554 i = vectorizedMismatch( 555 a, aOffset, 556 b, bOffset, 557 length, LOG2_ARRAY_DOUBLE_INDEX_SCALE); 558 } 559 if (i >= 0) { 560 // Check if mismatch is not associated with two NaN values 561 if (!Double.isNaN(a[aFromIndex + i]) || !Double.isNaN(b[bFromIndex + i])) 562 return i; 563 564 // Mismatch on two different NaN values that are normalized to match 565 // Fall back to slow mechanism 566 // ISSUE: Consider looping over vectorizedMismatch adjusting ranges 567 // However, requires that returned value be relative to input ranges 568 i++; 569 for (; i < length; i++) { 570 if (Double.doubleToLongBits(a[aFromIndex + i]) != Double.doubleToLongBits(b[bFromIndex + i])) 571 return i; 572 } 573 } 574 575 return -1; 576 } 577 578 /** 579 * A soft maximum array length imposed by array growth computations. 580 * Some JVMs (such as HotSpot) have an implementation limit that will cause 581 * 582 * OutOfMemoryError("Requested array size exceeds VM limit") 583 * 584 * to be thrown if a request is made to allocate an array of some length near 585 * Integer.MAX_VALUE, even if there is sufficient heap available. The actual 586 * limit might depend on some JVM implementation-specific characteristics such 587 * as the object header size. The soft maximum value is chosen conservatively so 588 * as to be smaller than any implementation limit that is likely to be encountered. 589 */ 590 public static final int SOFT_MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8; 591 592 /** 593 * Computes a new array length given an array's current length, a minimum growth 594 * amount, and a preferred growth amount. The computation is done in an overflow-safe 595 * fashion. 596 * 597 * This method is used by objects that contain an array that might need to be grown 598 * in order to fulfill some immediate need (the minimum growth amount) but would also 599 * like to request more space (the preferred growth amount) in order to accommodate 600 * potential future needs. The returned length is usually clamped at the soft maximum 601 * length in order to avoid hitting the JVM implementation limit. However, the soft 602 * maximum will be exceeded if the minimum growth amount requires it. 603 * 604 * If the preferred growth amount is less than the minimum growth amount, the 605 * minimum growth amount is used as the preferred growth amount. 606 * 607 * The preferred length is determined by adding the preferred growth amount to the 608 * current length. If the preferred length does not exceed the soft maximum length 609 * (SOFT_MAX_ARRAY_LENGTH) then the preferred length is returned. 610 * 611 * If the preferred length exceeds the soft maximum, we use the minimum growth 612 * amount. The minimum required length is determined by adding the minimum growth 613 * amount to the current length. If the minimum required length exceeds Integer.MAX_VALUE, 614 * then this method throws OutOfMemoryError. Otherwise, this method returns the greater of 615 * the soft maximum or the minimum required length. 616 * 617 * Note that this method does not do any array allocation itself; it only does array 618 * length growth computations. However, it will throw OutOfMemoryError as noted above. 619 * 620 * Note also that this method cannot detect the JVM's implementation limit, and it 621 * may compute and return a length value up to and including Integer.MAX_VALUE that 622 * might exceed the JVM's implementation limit. In that case, the caller will likely 623 * attempt an array allocation with that length and encounter an OutOfMemoryError. 624 * Of course, regardless of the length value returned from this method, the caller 625 * may encounter OutOfMemoryError if there is insufficient heap to fulfill the request. 626 * 627 * @param oldLength current length of the array (must be nonnegative) 628 * @param minGrowth minimum required growth amount (must be positive) 629 * @param prefGrowth preferred growth amount 630 * @return the new array length 631 * @throws OutOfMemoryError if the new length would exceed Integer.MAX_VALUE 632 */ newLength(int oldLength, int minGrowth, int prefGrowth)633 public static int newLength(int oldLength, int minGrowth, int prefGrowth) { 634 // preconditions not checked because of inlining 635 // assert oldLength >= 0 636 // assert minGrowth > 0 637 638 int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow 639 if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) { 640 return prefLength; 641 } else { 642 // put code cold in a separate method 643 return hugeLength(oldLength, minGrowth); 644 } 645 } 646 hugeLength(int oldLength, int minGrowth)647 private static int hugeLength(int oldLength, int minGrowth) { 648 int minLength = oldLength + minGrowth; 649 if (minLength < 0) { // overflow 650 throw new OutOfMemoryError( 651 "Required array length " + oldLength + " + " + minGrowth + " is too large"); 652 } else if (minLength <= SOFT_MAX_ARRAY_LENGTH) { 653 return SOFT_MAX_ARRAY_LENGTH; 654 } else { 655 return minLength; 656 } 657 } 658 } 659