1 /* 2 * Copyright (c) 2015, 2023, 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 java.util.Arrays; 28 import java.util.Collection; 29 import jdk.internal.misc.Unsafe; 30 import jdk.internal.vm.annotation.IntrinsicCandidate; 31 32 /** 33 * Utility methods to work with arrays. This includes a set of methods 34 * to find a mismatch between two primitive arrays. Also included is 35 * a method to calculate the new length of an array to be reallocated. 36 * 37 * <p>Array equality and lexicographical comparison can be built on top of 38 * array mismatch functionality. 39 * 40 * <p>The mismatch method implementation, {@link #vectorizedMismatch}, leverages 41 * vector-based techniques to access and compare the contents of two arrays. 42 * The Java implementation uses {@code Unsafe.getLongUnaligned} to access the 43 * content of an array, thus access is supported on platforms that do not 44 * support unaligned access. For a byte[] array, 8 bytes (64 bits) can be 45 * accessed and compared as a unit rather than individually, which increases 46 * the performance when the method is compiled by the HotSpot VM. On supported 47 * platforms the mismatch implementation is intrinsified to leverage SIMD 48 * instructions. So for a byte[] array, 16 bytes (128 bits), 32 bytes 49 * (256 bits), and perhaps in the future even 64 bytes (512 bits), platform 50 * permitting, can be accessed and compared as a unit, which further increases 51 * the performance over the Java implementation. 52 * 53 * <p>None of the mismatch methods perform array bounds checks. It is the 54 * responsibility of the caller (direct or otherwise) to perform such checks 55 * before calling this method. 56 */ 57 public class ArraysSupport { 58 static final Unsafe U = Unsafe.getUnsafe(); 59 60 // Android-changed: Android is little endian. 61 private static final boolean BIG_ENDIAN = false; 62 63 public static final int LOG2_ARRAY_BOOLEAN_INDEX_SCALE = exactLog2(Unsafe.ARRAY_BOOLEAN_INDEX_SCALE); 64 public static final int LOG2_ARRAY_BYTE_INDEX_SCALE = exactLog2(Unsafe.ARRAY_BYTE_INDEX_SCALE); 65 public static final int LOG2_ARRAY_CHAR_INDEX_SCALE = exactLog2(Unsafe.ARRAY_CHAR_INDEX_SCALE); 66 public static final int LOG2_ARRAY_SHORT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_SHORT_INDEX_SCALE); 67 public static final int LOG2_ARRAY_INT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_INT_INDEX_SCALE); 68 public static final int LOG2_ARRAY_LONG_INDEX_SCALE = exactLog2(Unsafe.ARRAY_LONG_INDEX_SCALE); 69 public static final int LOG2_ARRAY_FLOAT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_FLOAT_INDEX_SCALE); 70 public static final int LOG2_ARRAY_DOUBLE_INDEX_SCALE = exactLog2(Unsafe.ARRAY_DOUBLE_INDEX_SCALE); 71 72 private static final int LOG2_BYTE_BIT_SIZE = exactLog2(Byte.SIZE); 73 exactLog2(int scale)74 private static int exactLog2(int scale) { 75 if ((scale & (scale - 1)) != 0) 76 throw new Error("data type scale not a power of two"); 77 return Integer.numberOfTrailingZeros(scale); 78 } 79 ArraysSupport()80 private ArraysSupport() {} 81 82 /** 83 * Find the relative index of the first mismatching pair of elements in two 84 * primitive arrays of the same component type. Pairs of elements will be 85 * tested in order relative to given offsets into both arrays. 86 * 87 * <p>This method does not perform type checks or bounds checks. It is the 88 * responsibility of the caller to perform such checks before calling this 89 * method. 90 * 91 * <p>The given offsets, in bytes, need not be aligned according to the 92 * given log<sub>2</sub> size the array elements. More specifically, an 93 * offset modulus the size need not be zero. 94 * 95 * @param a the first array to be tested for mismatch, or {@code null} for 96 * direct memory access 97 * @param aOffset the relative offset, in bytes, from the base address of 98 * the first array to test from, otherwise if the first array is 99 * {@code null}, an absolute address pointing to the first element to test. 100 * @param b the second array to be tested for mismatch, or {@code null} for 101 * direct memory access 102 * @param bOffset the relative offset, in bytes, from the base address of 103 * the second array to test from, otherwise if the second array is 104 * {@code null}, an absolute address pointing to the first element to test. 105 * @param length the number of array elements to test 106 * @param log2ArrayIndexScale log<sub>2</sub> of the array index scale, that 107 * corresponds to the size, in bytes, of an array element. 108 * @return if a mismatch is found a relative index, between 0 (inclusive) 109 * and {@code length} (exclusive), of the first mismatching pair of elements 110 * in the two arrays. Otherwise, if a mismatch is not found the bitwise 111 * compliment of the number of remaining pairs of elements to be checked in 112 * the tail of the two arrays. 113 */ 114 @IntrinsicCandidate vectorizedMismatch(Object a, long aOffset, Object b, long bOffset, int length, int log2ArrayIndexScale)115 public static int vectorizedMismatch(Object a, long aOffset, 116 Object b, long bOffset, 117 int length, 118 int log2ArrayIndexScale) { 119 // assert a.getClass().isArray(); 120 // assert b.getClass().isArray(); 121 // assert 0 <= length <= sizeOf(a) 122 // assert 0 <= length <= sizeOf(b) 123 // assert 0 <= log2ArrayIndexScale <= 3 124 125 int log2ValuesPerWidth = LOG2_ARRAY_LONG_INDEX_SCALE - log2ArrayIndexScale; 126 int wi = 0; 127 for (; wi < length >> log2ValuesPerWidth; wi++) { 128 long bi = ((long) wi) << LOG2_ARRAY_LONG_INDEX_SCALE; 129 long av = U.getLongUnaligned(a, aOffset + bi); 130 long bv = U.getLongUnaligned(b, bOffset + bi); 131 if (av != bv) { 132 long x = av ^ bv; 133 int o = BIG_ENDIAN 134 ? Long.numberOfLeadingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale) 135 : Long.numberOfTrailingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale); 136 return (wi << log2ValuesPerWidth) + o; 137 } 138 } 139 140 // Calculate the tail of remaining elements to check 141 int tail = length - (wi << log2ValuesPerWidth); 142 143 if (log2ArrayIndexScale < LOG2_ARRAY_INT_INDEX_SCALE) { 144 int wordTail = 1 << (LOG2_ARRAY_INT_INDEX_SCALE - log2ArrayIndexScale); 145 // Handle 4 bytes or 2 chars in the tail using int width 146 if (tail >= wordTail) { 147 long bi = ((long) wi) << LOG2_ARRAY_LONG_INDEX_SCALE; 148 int av = U.getIntUnaligned(a, aOffset + bi); 149 int bv = U.getIntUnaligned(b, bOffset + bi); 150 if (av != bv) { 151 int x = av ^ bv; 152 int o = BIG_ENDIAN 153 ? Integer.numberOfLeadingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale) 154 : Integer.numberOfTrailingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale); 155 return (wi << log2ValuesPerWidth) + o; 156 } 157 tail -= wordTail; 158 } 159 return ~tail; 160 } 161 else { 162 return ~tail; 163 } 164 } 165 166 // Possible values for the type operand of the NEWARRAY instruction. 167 // See https://docs.oracle.com/javase/specs/jvms/se9/html/jvms-6.html#jvms-6.5.newarray. 168 169 public static final int T_BOOLEAN = 4; 170 public static final int T_CHAR = 5; 171 public static final int T_FLOAT = 6; 172 public static final int T_DOUBLE = 7; 173 public static final int T_BYTE = 8; 174 public static final int T_SHORT = 9; 175 public static final int T_INT = 10; 176 public static final int T_LONG = 11; 177 178 /** 179 * Calculate the hash code for an array in a way that enables efficient 180 * vectorization. 181 * 182 * <p>This method does not perform type checks or bounds checks. It is the 183 * responsibility of the caller to perform such checks before calling this 184 * method. 185 * 186 * @param array for which to calculate hash code 187 * @param fromIndex start index, scaled to basicType 188 * @param length number of elements to include in the hash 189 * @param initialValue the initial value for the hash (typically constant 0 or 1) 190 * @param basicType type constant denoting how to interpret the array content. 191 * T_BOOLEAN is used to signify unsigned bytes, and T_CHAR might be used 192 * even if array is a byte[]. 193 * @implNote currently basicType must be constant at the call site for this method 194 * to be intrinsified. 195 * 196 * @return the calculated hash value 197 */ 198 @IntrinsicCandidate vectorizedHashCode(Object array, int fromIndex, int length, int initialValue, int basicType)199 public static int vectorizedHashCode(Object array, int fromIndex, int length, int initialValue, 200 int basicType) { 201 return switch (basicType) { 202 case T_BOOLEAN -> signedHashCode(initialValue, (byte[]) array, fromIndex, length); 203 case T_CHAR -> array instanceof byte[] 204 ? utf16hashCode(initialValue, (byte[]) array, fromIndex, length) 205 : hashCode(initialValue, (char[]) array, fromIndex, length); 206 case T_BYTE -> hashCode(initialValue, (byte[]) array, fromIndex, length); 207 case T_SHORT -> hashCode(initialValue, (short[]) array, fromIndex, length); 208 case T_INT -> hashCode(initialValue, (int[]) array, fromIndex, length); 209 default -> throw new IllegalArgumentException("unrecognized basic type: " + basicType); 210 }; 211 } 212 signedHashCode(int result, byte[] a, int fromIndex, int length)213 private static int signedHashCode(int result, byte[] a, int fromIndex, int length) { 214 int end = fromIndex + length; 215 for (int i = fromIndex; i < end; i++) { 216 result = 31 * result + (a[i] & 0xff); 217 } 218 return result; 219 } 220 hashCode(int result, byte[] a, int fromIndex, int length)221 private static int hashCode(int result, byte[] a, int fromIndex, int length) { 222 int end = fromIndex + length; 223 for (int i = fromIndex; i < end; i++) { 224 result = 31 * result + a[i]; 225 } 226 return result; 227 } 228 hashCode(int result, char[] a, int fromIndex, int length)229 private static int hashCode(int result, char[] a, int fromIndex, int length) { 230 int end = fromIndex + length; 231 for (int i = fromIndex; i < end; i++) { 232 result = 31 * result + a[i]; 233 } 234 return result; 235 } 236 hashCode(int result, short[] a, int fromIndex, int length)237 private static int hashCode(int result, short[] a, int fromIndex, int length) { 238 int end = fromIndex + length; 239 for (int i = fromIndex; i < end; i++) { 240 result = 31 * result + a[i]; 241 } 242 return result; 243 } 244 hashCode(int result, int[] a, int fromIndex, int length)245 private static int hashCode(int result, int[] a, int fromIndex, int length) { 246 int end = fromIndex + length; 247 for (int i = fromIndex; i < end; i++) { 248 result = 31 * result + a[i]; 249 } 250 return result; 251 } 252 253 // Android-removed: Make the StringUTF16 public on Android, and avoid JavaLangAccess. 254 // private static final JavaLangAccess JLA = SharedSecrets.getJavaLangAccess(); 255 /* 256 * fromIndex and length must be scaled to char indexes. 257 */ utf16hashCode(int result, byte[] value, int fromIndex, int length)258 public static int utf16hashCode(int result, byte[] value, int fromIndex, int length) { 259 int end = fromIndex + length; 260 for (int i = fromIndex; i < end; i++) { 261 // Android-removed: Make the StringUTF16 public on Android, and avoid JavaLangAccess. 262 // result = 31 * result + JLA.getUTF16Char(value, i); 263 result = 31 * result + StringUTF16.getChar(value, i); 264 265 } 266 return result; 267 } 268 269 // Booleans 270 // Each boolean element takes up one byte 271 mismatch(boolean[] a, boolean[] b, int length)272 public static int mismatch(boolean[] a, 273 boolean[] b, 274 int length) { 275 int i = 0; 276 if (length > 7) { 277 if (a[0] != b[0]) 278 return 0; 279 i = vectorizedMismatch( 280 a, Unsafe.ARRAY_BOOLEAN_BASE_OFFSET, 281 b, Unsafe.ARRAY_BOOLEAN_BASE_OFFSET, 282 length, LOG2_ARRAY_BOOLEAN_INDEX_SCALE); 283 if (i >= 0) 284 return i; 285 i = length - ~i; 286 } 287 for (; i < length; i++) { 288 if (a[i] != b[i]) 289 return i; 290 } 291 return -1; 292 } 293 mismatch(boolean[] a, int aFromIndex, boolean[] b, int bFromIndex, int length)294 public static int mismatch(boolean[] a, int aFromIndex, 295 boolean[] b, int bFromIndex, 296 int length) { 297 int i = 0; 298 if (length > 7) { 299 if (a[aFromIndex] != b[bFromIndex]) 300 return 0; 301 int aOffset = Unsafe.ARRAY_BOOLEAN_BASE_OFFSET + aFromIndex; 302 int bOffset = Unsafe.ARRAY_BOOLEAN_BASE_OFFSET + bFromIndex; 303 i = vectorizedMismatch( 304 a, aOffset, 305 b, bOffset, 306 length, LOG2_ARRAY_BOOLEAN_INDEX_SCALE); 307 if (i >= 0) 308 return i; 309 i = length - ~i; 310 } 311 for (; i < length; i++) { 312 if (a[aFromIndex + i] != b[bFromIndex + i]) 313 return i; 314 } 315 return -1; 316 } 317 318 319 // Bytes 320 321 /** 322 * Find the index of a mismatch between two arrays. 323 * 324 * <p>This method does not perform bounds checks. It is the responsibility 325 * of the caller to perform such bounds checks before calling this method. 326 * 327 * @param a the first array to be tested for a mismatch 328 * @param b the second array to be tested for a mismatch 329 * @param length the number of bytes from each array to check 330 * @return the index of a mismatch between the two arrays, otherwise -1 if 331 * no mismatch. The index will be within the range of (inclusive) 0 to 332 * (exclusive) the smaller of the two array lengths. 333 */ mismatch(byte[] a, byte[] b, int length)334 public static int mismatch(byte[] a, 335 byte[] b, 336 int length) { 337 // ISSUE: defer to index receiving methods if performance is good 338 // assert length <= a.length 339 // assert length <= b.length 340 341 int i = 0; 342 if (length > 7) { 343 if (a[0] != b[0]) 344 return 0; 345 i = vectorizedMismatch( 346 a, Unsafe.ARRAY_BYTE_BASE_OFFSET, 347 b, Unsafe.ARRAY_BYTE_BASE_OFFSET, 348 length, LOG2_ARRAY_BYTE_INDEX_SCALE); 349 if (i >= 0) 350 return i; 351 // Align to tail 352 i = length - ~i; 353 // assert i >= 0 && i <= 7; 354 } 355 // Tail < 8 bytes 356 for (; i < length; i++) { 357 if (a[i] != b[i]) 358 return i; 359 } 360 return -1; 361 } 362 363 /** 364 * Find the relative index of a mismatch between two arrays starting from 365 * given indexes. 366 * 367 * <p>This method does not perform bounds checks. It is the responsibility 368 * of the caller to perform such bounds checks before calling this method. 369 * 370 * @param a the first array to be tested for a mismatch 371 * @param aFromIndex the index of the first element (inclusive) in the first 372 * array to be compared 373 * @param b the second array to be tested for a mismatch 374 * @param bFromIndex the index of the first element (inclusive) in the 375 * second array to be compared 376 * @param length the number of bytes from each array to check 377 * @return the relative index of a mismatch between the two arrays, 378 * otherwise -1 if no mismatch. The index will be within the range of 379 * (inclusive) 0 to (exclusive) the smaller of the two array bounds. 380 */ mismatch(byte[] a, int aFromIndex, byte[] b, int bFromIndex, int length)381 public static int mismatch(byte[] a, int aFromIndex, 382 byte[] b, int bFromIndex, 383 int length) { 384 // assert 0 <= aFromIndex < a.length 385 // assert 0 <= aFromIndex + length <= a.length 386 // assert 0 <= bFromIndex < b.length 387 // assert 0 <= bFromIndex + length <= b.length 388 // assert length >= 0 389 390 int i = 0; 391 if (length > 7) { 392 if (a[aFromIndex] != b[bFromIndex]) 393 return 0; 394 int aOffset = Unsafe.ARRAY_BYTE_BASE_OFFSET + aFromIndex; 395 int bOffset = Unsafe.ARRAY_BYTE_BASE_OFFSET + bFromIndex; 396 i = vectorizedMismatch( 397 a, aOffset, 398 b, bOffset, 399 length, LOG2_ARRAY_BYTE_INDEX_SCALE); 400 if (i >= 0) 401 return i; 402 i = length - ~i; 403 } 404 for (; i < length; i++) { 405 if (a[aFromIndex + i] != b[bFromIndex + i]) 406 return i; 407 } 408 return -1; 409 } 410 411 412 // Chars 413 mismatch(char[] a, char[] b, int length)414 public static int mismatch(char[] a, 415 char[] b, 416 int length) { 417 int i = 0; 418 if (length > 3) { 419 if (a[0] != b[0]) 420 return 0; 421 i = vectorizedMismatch( 422 a, Unsafe.ARRAY_CHAR_BASE_OFFSET, 423 b, Unsafe.ARRAY_CHAR_BASE_OFFSET, 424 length, LOG2_ARRAY_CHAR_INDEX_SCALE); 425 if (i >= 0) 426 return i; 427 i = length - ~i; 428 } 429 for (; i < length; i++) { 430 if (a[i] != b[i]) 431 return i; 432 } 433 return -1; 434 } 435 mismatch(char[] a, int aFromIndex, char[] b, int bFromIndex, int length)436 public static int mismatch(char[] a, int aFromIndex, 437 char[] b, int bFromIndex, 438 int length) { 439 int i = 0; 440 if (length > 3) { 441 if (a[aFromIndex] != b[bFromIndex]) 442 return 0; 443 int aOffset = Unsafe.ARRAY_CHAR_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_CHAR_INDEX_SCALE); 444 int bOffset = Unsafe.ARRAY_CHAR_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_CHAR_INDEX_SCALE); 445 i = vectorizedMismatch( 446 a, aOffset, 447 b, bOffset, 448 length, LOG2_ARRAY_CHAR_INDEX_SCALE); 449 if (i >= 0) 450 return i; 451 i = length - ~i; 452 } 453 for (; i < length; i++) { 454 if (a[aFromIndex + i] != b[bFromIndex + i]) 455 return i; 456 } 457 return -1; 458 } 459 460 461 // Shorts 462 mismatch(short[] a, short[] b, int length)463 public static int mismatch(short[] a, 464 short[] b, 465 int length) { 466 int i = 0; 467 if (length > 3) { 468 if (a[0] != b[0]) 469 return 0; 470 i = vectorizedMismatch( 471 a, Unsafe.ARRAY_SHORT_BASE_OFFSET, 472 b, Unsafe.ARRAY_SHORT_BASE_OFFSET, 473 length, LOG2_ARRAY_SHORT_INDEX_SCALE); 474 if (i >= 0) 475 return i; 476 i = length - ~i; 477 } 478 for (; i < length; i++) { 479 if (a[i] != b[i]) 480 return i; 481 } 482 return -1; 483 } 484 mismatch(short[] a, int aFromIndex, short[] b, int bFromIndex, int length)485 public static int mismatch(short[] a, int aFromIndex, 486 short[] b, int bFromIndex, 487 int length) { 488 int i = 0; 489 if (length > 3) { 490 if (a[aFromIndex] != b[bFromIndex]) 491 return 0; 492 int aOffset = Unsafe.ARRAY_SHORT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_SHORT_INDEX_SCALE); 493 int bOffset = Unsafe.ARRAY_SHORT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_SHORT_INDEX_SCALE); 494 i = vectorizedMismatch( 495 a, aOffset, 496 b, bOffset, 497 length, LOG2_ARRAY_SHORT_INDEX_SCALE); 498 if (i >= 0) 499 return i; 500 i = length - ~i; 501 } 502 for (; i < length; i++) { 503 if (a[aFromIndex + i] != b[bFromIndex + i]) 504 return i; 505 } 506 return -1; 507 } 508 509 510 // Ints 511 mismatch(int[] a, int[] b, int length)512 public static int mismatch(int[] a, 513 int[] b, 514 int length) { 515 int i = 0; 516 if (length > 1) { 517 if (a[0] != b[0]) 518 return 0; 519 i = vectorizedMismatch( 520 a, Unsafe.ARRAY_INT_BASE_OFFSET, 521 b, Unsafe.ARRAY_INT_BASE_OFFSET, 522 length, LOG2_ARRAY_INT_INDEX_SCALE); 523 if (i >= 0) 524 return i; 525 i = length - ~i; 526 } 527 for (; i < length; i++) { 528 if (a[i] != b[i]) 529 return i; 530 } 531 return -1; 532 } 533 mismatch(int[] a, int aFromIndex, int[] b, int bFromIndex, int length)534 public static int mismatch(int[] a, int aFromIndex, 535 int[] b, int bFromIndex, 536 int length) { 537 int i = 0; 538 if (length > 1) { 539 if (a[aFromIndex] != b[bFromIndex]) 540 return 0; 541 int aOffset = Unsafe.ARRAY_INT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_INT_INDEX_SCALE); 542 int bOffset = Unsafe.ARRAY_INT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_INT_INDEX_SCALE); 543 i = vectorizedMismatch( 544 a, aOffset, 545 b, bOffset, 546 length, LOG2_ARRAY_INT_INDEX_SCALE); 547 if (i >= 0) 548 return i; 549 i = length - ~i; 550 } 551 for (; i < length; i++) { 552 if (a[aFromIndex + i] != b[bFromIndex + i]) 553 return i; 554 } 555 return -1; 556 } 557 558 559 // Floats 560 mismatch(float[] a, float[] b, int length)561 public static int mismatch(float[] a, 562 float[] b, 563 int length) { 564 return mismatch(a, 0, b, 0, length); 565 } 566 mismatch(float[] a, int aFromIndex, float[] b, int bFromIndex, int length)567 public static int mismatch(float[] a, int aFromIndex, 568 float[] b, int bFromIndex, 569 int length) { 570 int i = 0; 571 if (length > 1) { 572 if (Float.floatToRawIntBits(a[aFromIndex]) == Float.floatToRawIntBits(b[bFromIndex])) { 573 int aOffset = Unsafe.ARRAY_FLOAT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_FLOAT_INDEX_SCALE); 574 int bOffset = Unsafe.ARRAY_FLOAT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_FLOAT_INDEX_SCALE); 575 i = vectorizedMismatch( 576 a, aOffset, 577 b, bOffset, 578 length, LOG2_ARRAY_FLOAT_INDEX_SCALE); 579 } 580 // Mismatched 581 if (i >= 0) { 582 // Check if mismatch is not associated with two NaN values 583 if (!Float.isNaN(a[aFromIndex + i]) || !Float.isNaN(b[bFromIndex + i])) 584 return i; 585 586 // Mismatch on two different NaN values that are normalized to match 587 // Fall back to slow mechanism 588 // ISSUE: Consider looping over vectorizedMismatch adjusting ranges 589 // However, requires that returned value be relative to input ranges 590 i++; 591 } 592 // Matched 593 else { 594 i = length - ~i; 595 } 596 } 597 for (; i < length; i++) { 598 if (Float.floatToIntBits(a[aFromIndex + i]) != Float.floatToIntBits(b[bFromIndex + i])) 599 return i; 600 } 601 return -1; 602 } 603 604 // 64 bit sizes 605 606 // Long 607 mismatch(long[] a, long[] b, int length)608 public static int mismatch(long[] a, 609 long[] b, 610 int length) { 611 if (length == 0) { 612 return -1; 613 } 614 if (a[0] != b[0]) 615 return 0; 616 int i = vectorizedMismatch( 617 a, Unsafe.ARRAY_LONG_BASE_OFFSET, 618 b, Unsafe.ARRAY_LONG_BASE_OFFSET, 619 length, LOG2_ARRAY_LONG_INDEX_SCALE); 620 return i >= 0 ? i : -1; 621 } 622 mismatch(long[] a, int aFromIndex, long[] b, int bFromIndex, int length)623 public static int mismatch(long[] a, int aFromIndex, 624 long[] b, int bFromIndex, 625 int length) { 626 if (length == 0) { 627 return -1; 628 } 629 if (a[aFromIndex] != b[bFromIndex]) 630 return 0; 631 int aOffset = Unsafe.ARRAY_LONG_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_LONG_INDEX_SCALE); 632 int bOffset = Unsafe.ARRAY_LONG_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_LONG_INDEX_SCALE); 633 int i = vectorizedMismatch( 634 a, aOffset, 635 b, bOffset, 636 length, LOG2_ARRAY_LONG_INDEX_SCALE); 637 return i >= 0 ? i : -1; 638 } 639 640 641 // Double 642 mismatch(double[] a, double[] b, int length)643 public static int mismatch(double[] a, 644 double[] b, 645 int length) { 646 return mismatch(a, 0, b, 0, length); 647 } 648 mismatch(double[] a, int aFromIndex, double[] b, int bFromIndex, int length)649 public static int mismatch(double[] a, int aFromIndex, 650 double[] b, int bFromIndex, 651 int length) { 652 if (length == 0) { 653 return -1; 654 } 655 int i = 0; 656 if (Double.doubleToRawLongBits(a[aFromIndex]) == Double.doubleToRawLongBits(b[bFromIndex])) { 657 int aOffset = Unsafe.ARRAY_DOUBLE_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_DOUBLE_INDEX_SCALE); 658 int bOffset = Unsafe.ARRAY_DOUBLE_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_DOUBLE_INDEX_SCALE); 659 i = vectorizedMismatch( 660 a, aOffset, 661 b, bOffset, 662 length, LOG2_ARRAY_DOUBLE_INDEX_SCALE); 663 } 664 if (i >= 0) { 665 // Check if mismatch is not associated with two NaN values 666 if (!Double.isNaN(a[aFromIndex + i]) || !Double.isNaN(b[bFromIndex + i])) 667 return i; 668 669 // Mismatch on two different NaN values that are normalized to match 670 // Fall back to slow mechanism 671 // ISSUE: Consider looping over vectorizedMismatch adjusting ranges 672 // However, requires that returned value be relative to input ranges 673 i++; 674 for (; i < length; i++) { 675 if (Double.doubleToLongBits(a[aFromIndex + i]) != Double.doubleToLongBits(b[bFromIndex + i])) 676 return i; 677 } 678 } 679 680 return -1; 681 } 682 683 /** 684 * A soft maximum array length imposed by array growth computations. 685 * Some JVMs (such as HotSpot) have an implementation limit that will cause 686 * 687 * OutOfMemoryError("Requested array size exceeds VM limit") 688 * 689 * to be thrown if a request is made to allocate an array of some length near 690 * Integer.MAX_VALUE, even if there is sufficient heap available. The actual 691 * limit might depend on some JVM implementation-specific characteristics such 692 * as the object header size. The soft maximum value is chosen conservatively so 693 * as to be smaller than any implementation limit that is likely to be encountered. 694 */ 695 public static final int SOFT_MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8; 696 697 /** 698 * Computes a new array length given an array's current length, a minimum growth 699 * amount, and a preferred growth amount. The computation is done in an overflow-safe 700 * fashion. 701 * 702 * This method is used by objects that contain an array that might need to be grown 703 * in order to fulfill some immediate need (the minimum growth amount) but would also 704 * like to request more space (the preferred growth amount) in order to accommodate 705 * potential future needs. The returned length is usually clamped at the soft maximum 706 * length in order to avoid hitting the JVM implementation limit. However, the soft 707 * maximum will be exceeded if the minimum growth amount requires it. 708 * 709 * If the preferred growth amount is less than the minimum growth amount, the 710 * minimum growth amount is used as the preferred growth amount. 711 * 712 * The preferred length is determined by adding the preferred growth amount to the 713 * current length. If the preferred length does not exceed the soft maximum length 714 * (SOFT_MAX_ARRAY_LENGTH) then the preferred length is returned. 715 * 716 * If the preferred length exceeds the soft maximum, we use the minimum growth 717 * amount. The minimum required length is determined by adding the minimum growth 718 * amount to the current length. If the minimum required length exceeds Integer.MAX_VALUE, 719 * then this method throws OutOfMemoryError. Otherwise, this method returns the greater of 720 * the soft maximum or the minimum required length. 721 * 722 * Note that this method does not do any array allocation itself; it only does array 723 * length growth computations. However, it will throw OutOfMemoryError as noted above. 724 * 725 * Note also that this method cannot detect the JVM's implementation limit, and it 726 * may compute and return a length value up to and including Integer.MAX_VALUE that 727 * might exceed the JVM's implementation limit. In that case, the caller will likely 728 * attempt an array allocation with that length and encounter an OutOfMemoryError. 729 * Of course, regardless of the length value returned from this method, the caller 730 * may encounter OutOfMemoryError if there is insufficient heap to fulfill the request. 731 * 732 * @param oldLength current length of the array (must be nonnegative) 733 * @param minGrowth minimum required growth amount (must be positive) 734 * @param prefGrowth preferred growth amount 735 * @return the new array length 736 * @throws OutOfMemoryError if the new length would exceed Integer.MAX_VALUE 737 */ newLength(int oldLength, int minGrowth, int prefGrowth)738 public static int newLength(int oldLength, int minGrowth, int prefGrowth) { 739 // preconditions not checked because of inlining 740 // assert oldLength >= 0 741 // assert minGrowth > 0 742 743 int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow 744 if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) { 745 return prefLength; 746 } else { 747 // put code cold in a separate method 748 return hugeLength(oldLength, minGrowth); 749 } 750 } 751 hugeLength(int oldLength, int minGrowth)752 private static int hugeLength(int oldLength, int minGrowth) { 753 int minLength = oldLength + minGrowth; 754 if (minLength < 0) { // overflow 755 throw new OutOfMemoryError( 756 "Required array length " + oldLength + " + " + minGrowth + " is too large"); 757 } else if (minLength <= SOFT_MAX_ARRAY_LENGTH) { 758 return SOFT_MAX_ARRAY_LENGTH; 759 } else { 760 return minLength; 761 } 762 } 763 764 /** 765 * Reverses the elements of an array in-place. 766 * 767 * @param <T> the array component type 768 * @param a the array to be reversed 769 * @return the reversed array, always the same array as the argument 770 */ reverse(T[] a)771 public static <T> T[] reverse(T[] a) { 772 int limit = a.length / 2; 773 for (int i = 0, j = a.length - 1; i < limit; i++, j--) { 774 T t = a[i]; 775 a[i] = a[j]; 776 a[j] = t; 777 } 778 return a; 779 } 780 781 /** 782 * Dump the contents of the given collection into the given array, in reverse order. 783 * This mirrors the semantics of Collection.toArray(T[]) in regard to reusing the given 784 * array, appending null if necessary, or allocating a new array of the same component type. 785 * <p> 786 * A constraint is that this method should issue exactly one method call on the collection 787 * to obtain the elements and the size. Having a separate size() call or using an Iterator 788 * could result in errors if the collection changes size between calls. This implies that 789 * the elements need to be obtained via a single call to one of the toArray() methods. 790 * This further implies allocating memory proportional to the number of elements and 791 * making an extra copy, but this seems unavoidable. 792 * <p> 793 * An obvious approach would be simply to call coll.toArray(array) and then reverse the 794 * order of the elements. This doesn't work, because if given array is sufficiently long, 795 * we cannot tell how many elements were copied into it and thus there is no way to reverse 796 * the right set of elements while leaving the remaining array elements undisturbed. 797 * 798 * @throws ArrayStoreException if coll contains elements that can't be stored in the array 799 */ toArrayReversed(Collection<?> coll, T[] array)800 public static <T> T[] toArrayReversed(Collection<?> coll, T[] array) { 801 T[] newArray = reverse(coll.toArray(Arrays.copyOfRange(array, 0, 0))); 802 if (newArray.length > array.length) { 803 return newArray; 804 } else { 805 System.arraycopy(newArray, 0, array, 0, newArray.length); 806 if (array.length > newArray.length) { 807 array[newArray.length] = null; 808 } 809 return array; 810 } 811 } 812 } 813