1 /* 2 * Copyright (c) 2016, 2020, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package java.util; 27 28 import java.io.IOException; 29 import java.io.InvalidObjectException; 30 import java.io.ObjectInputStream; 31 import java.io.ObjectOutputStream; 32 import java.io.ObjectStreamException; 33 import java.io.Serializable; 34 import java.lang.reflect.Array; 35 import java.util.function.BiFunction; 36 import java.util.function.Function; 37 import java.util.function.Predicate; 38 import java.util.function.UnaryOperator; 39 import jdk.internal.access.SharedSecrets; 40 import jdk.internal.misc.VM; 41 import jdk.internal.vm.annotation.Stable; 42 43 /** 44 * Container class for immutable collections. Not part of the public API. 45 * Mainly for namespace management and shared infrastructure. 46 * 47 * Serial warnings are suppressed throughout because all implementation 48 * classes use a serial proxy and thus have no need to declare serialVersionUID. 49 */ 50 @SuppressWarnings("serial") 51 class ImmutableCollections { 52 /** 53 * A "salt" value used for randomizing iteration order. This is initialized once 54 * and stays constant for the lifetime of the JVM. It need not be truly random, but 55 * it needs to vary sufficiently from one run to the next so that iteration order 56 * will vary between JVM runs. 57 */ 58 private static final long SALT32L; 59 60 /** 61 * For set and map iteration, we will iterate in "reverse" stochastically, 62 * decided at bootstrap time. 63 */ 64 private static final boolean REVERSE; 65 static { 66 // to generate a reasonably random and well-mixed SALT, use an arbitrary 67 // value (a slice of pi), multiply with a random seed, then pick 68 // the mid 32-bits from the product. By picking a SALT value in the 69 // [0 ... 0xFFFF_FFFFL == 2^32-1] range, we ensure that for any positive 70 // int N, (SALT32L * N) >> 32 is a number in the [0 ... N-1] range. This 71 // property will be used to avoid more expensive modulo-based 72 // calculations. 73 long color = 0x243F_6A88_85A3_08D3L; // slice of pi 74 75 // When running with -Xshare:dump, the VM will supply a "random" seed that's 76 // derived from the JVM build/version, so can we generate the exact same 77 // CDS archive for the same JDK build. This makes it possible to verify the 78 // consistency of the JDK build. 79 long seed = VM.getRandomSeedForCDSDump(); 80 if (seed == 0) { 81 seed = System.nanoTime(); 82 } 83 SALT32L = (int)((color * seed) >> 16) & 0xFFFF_FFFFL; 84 // use the lowest bit to determine if we should reverse iteration 85 REVERSE = (SALT32L & 1) == 0; 86 } 87 88 /** 89 * Constants following this might be initialized from the CDS archive via 90 * this array. 91 */ 92 private static Object[] archivedObjects; 93 94 private static final Object EMPTY; 95 96 static final ListN<?> EMPTY_LIST; 97 98 static final SetN<?> EMPTY_SET; 99 100 static final MapN<?,?> EMPTY_MAP; 101 102 static { 103 VM.initializeFromArchive(ImmutableCollections.class); 104 if (archivedObjects == null) { 105 EMPTY = new Object(); 106 EMPTY_LIST = new ListN<>(); 107 EMPTY_SET = new SetN<>(); 108 EMPTY_MAP = new MapN<>(); 109 archivedObjects = new Object[] { EMPTY, EMPTY_LIST, EMPTY_SET, EMPTY_MAP }; 110 } else { 111 EMPTY = archivedObjects[0]; 112 EMPTY_LIST = (ListN)archivedObjects[1]; 113 EMPTY_SET = (SetN)archivedObjects[2]; 114 EMPTY_MAP = (MapN)archivedObjects[3]; 115 } 116 } 117 118 /** No instances. */ ImmutableCollections()119 private ImmutableCollections() { } 120 121 /** 122 * The reciprocal of load factor. Given a number of elements 123 * to store, multiply by this factor to get the table size. 124 */ 125 static final int EXPAND_FACTOR = 2; 126 uoe()127 static UnsupportedOperationException uoe() { return new UnsupportedOperationException(); } 128 129 static abstract class AbstractImmutableCollection<E> extends AbstractCollection<E> { 130 // all mutating methods throw UnsupportedOperationException add(E e)131 @Override public boolean add(E e) { throw uoe(); } addAll(Collection<? extends E> c)132 @Override public boolean addAll(Collection<? extends E> c) { throw uoe(); } clear()133 @Override public void clear() { throw uoe(); } remove(Object o)134 @Override public boolean remove(Object o) { throw uoe(); } removeAll(Collection<?> c)135 @Override public boolean removeAll(Collection<?> c) { throw uoe(); } removeIf(Predicate<? super E> filter)136 @Override public boolean removeIf(Predicate<? super E> filter) { throw uoe(); } retainAll(Collection<?> c)137 @Override public boolean retainAll(Collection<?> c) { throw uoe(); } 138 } 139 140 // ---------- List Implementations ---------- 141 142 // make a copy, short-circuiting based on implementation class 143 @SuppressWarnings("unchecked") listCopy(Collection<? extends E> coll)144 static <E> List<E> listCopy(Collection<? extends E> coll) { 145 if (coll instanceof AbstractImmutableList && coll.getClass() != SubList.class) { 146 return (List<E>)coll; 147 } else { 148 return (List<E>)List.of(coll.toArray()); 149 } 150 } 151 152 static abstract class AbstractImmutableList<E> extends AbstractImmutableCollection<E> 153 implements List<E>, RandomAccess { 154 155 // all mutating methods throw UnsupportedOperationException add(int index, E element)156 @Override public void add(int index, E element) { throw uoe(); } addAll(int index, Collection<? extends E> c)157 @Override public boolean addAll(int index, Collection<? extends E> c) { throw uoe(); } remove(int index)158 @Override public E remove(int index) { throw uoe(); } replaceAll(UnaryOperator<E> operator)159 @Override public void replaceAll(UnaryOperator<E> operator) { throw uoe(); } set(int index, E element)160 @Override public E set(int index, E element) { throw uoe(); } sort(Comparator<? super E> c)161 @Override public void sort(Comparator<? super E> c) { throw uoe(); } 162 163 @Override subList(int fromIndex, int toIndex)164 public List<E> subList(int fromIndex, int toIndex) { 165 int size = size(); 166 subListRangeCheck(fromIndex, toIndex, size); 167 return SubList.fromList(this, fromIndex, toIndex); 168 } 169 subListRangeCheck(int fromIndex, int toIndex, int size)170 static void subListRangeCheck(int fromIndex, int toIndex, int size) { 171 if (fromIndex < 0) 172 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); 173 if (toIndex > size) 174 throw new IndexOutOfBoundsException("toIndex = " + toIndex); 175 if (fromIndex > toIndex) 176 throw new IllegalArgumentException("fromIndex(" + fromIndex + 177 ") > toIndex(" + toIndex + ")"); 178 } 179 180 @Override iterator()181 public Iterator<E> iterator() { 182 return new ListItr<E>(this, size()); 183 } 184 185 @Override listIterator()186 public ListIterator<E> listIterator() { 187 return listIterator(0); 188 } 189 190 @Override listIterator(final int index)191 public ListIterator<E> listIterator(final int index) { 192 int size = size(); 193 if (index < 0 || index > size) { 194 throw outOfBounds(index); 195 } 196 return new ListItr<E>(this, size, index); 197 } 198 199 @Override equals(Object o)200 public boolean equals(Object o) { 201 if (o == this) { 202 return true; 203 } 204 205 if (!(o instanceof List)) { 206 return false; 207 } 208 209 Iterator<?> oit = ((List<?>) o).iterator(); 210 for (int i = 0, s = size(); i < s; i++) { 211 if (!oit.hasNext() || !get(i).equals(oit.next())) { 212 return false; 213 } 214 } 215 return !oit.hasNext(); 216 } 217 218 @Override indexOf(Object o)219 public int indexOf(Object o) { 220 Objects.requireNonNull(o); 221 for (int i = 0, s = size(); i < s; i++) { 222 if (o.equals(get(i))) { 223 return i; 224 } 225 } 226 return -1; 227 } 228 229 @Override lastIndexOf(Object o)230 public int lastIndexOf(Object o) { 231 Objects.requireNonNull(o); 232 for (int i = size() - 1; i >= 0; i--) { 233 if (o.equals(get(i))) { 234 return i; 235 } 236 } 237 return -1; 238 } 239 240 @Override hashCode()241 public int hashCode() { 242 int hash = 1; 243 for (int i = 0, s = size(); i < s; i++) { 244 hash = 31 * hash + get(i).hashCode(); 245 } 246 return hash; 247 } 248 249 @Override contains(Object o)250 public boolean contains(Object o) { 251 return indexOf(o) >= 0; 252 } 253 outOfBounds(int index)254 IndexOutOfBoundsException outOfBounds(int index) { 255 return new IndexOutOfBoundsException("Index: " + index + " Size: " + size()); 256 } 257 } 258 259 static final class ListItr<E> implements ListIterator<E> { 260 261 @Stable 262 private final List<E> list; 263 264 @Stable 265 private final int size; 266 267 @Stable 268 private final boolean isListIterator; 269 270 private int cursor; 271 ListItr(List<E> list, int size)272 ListItr(List<E> list, int size) { 273 this.list = list; 274 this.size = size; 275 this.cursor = 0; 276 isListIterator = false; 277 } 278 ListItr(List<E> list, int size, int index)279 ListItr(List<E> list, int size, int index) { 280 this.list = list; 281 this.size = size; 282 this.cursor = index; 283 isListIterator = true; 284 } 285 hasNext()286 public boolean hasNext() { 287 return cursor != size; 288 } 289 next()290 public E next() { 291 try { 292 int i = cursor; 293 E next = list.get(i); 294 cursor = i + 1; 295 return next; 296 } catch (IndexOutOfBoundsException e) { 297 throw new NoSuchElementException(); 298 } 299 } 300 remove()301 public void remove() { 302 throw uoe(); 303 } 304 hasPrevious()305 public boolean hasPrevious() { 306 if (!isListIterator) { 307 throw uoe(); 308 } 309 return cursor != 0; 310 } 311 previous()312 public E previous() { 313 if (!isListIterator) { 314 throw uoe(); 315 } 316 try { 317 int i = cursor - 1; 318 E previous = list.get(i); 319 cursor = i; 320 return previous; 321 } catch (IndexOutOfBoundsException e) { 322 throw new NoSuchElementException(); 323 } 324 } 325 nextIndex()326 public int nextIndex() { 327 if (!isListIterator) { 328 throw uoe(); 329 } 330 return cursor; 331 } 332 previousIndex()333 public int previousIndex() { 334 if (!isListIterator) { 335 throw uoe(); 336 } 337 return cursor - 1; 338 } 339 set(E e)340 public void set(E e) { 341 throw uoe(); 342 } 343 add(E e)344 public void add(E e) { 345 throw uoe(); 346 } 347 } 348 349 static final class SubList<E> extends AbstractImmutableList<E> 350 implements RandomAccess { 351 352 @Stable 353 private final List<E> root; 354 355 @Stable 356 private final int offset; 357 358 @Stable 359 private final int size; 360 SubList(List<E> root, int offset, int size)361 private SubList(List<E> root, int offset, int size) { 362 this.root = root; 363 this.offset = offset; 364 this.size = size; 365 } 366 367 /** 368 * Constructs a sublist of another SubList. 369 */ fromSubList(SubList<E> parent, int fromIndex, int toIndex)370 static <E> SubList<E> fromSubList(SubList<E> parent, int fromIndex, int toIndex) { 371 return new SubList<>(parent.root, parent.offset + fromIndex, toIndex - fromIndex); 372 } 373 374 /** 375 * Constructs a sublist of an arbitrary AbstractImmutableList, which is 376 * not a SubList itself. 377 */ fromList(List<E> list, int fromIndex, int toIndex)378 static <E> SubList<E> fromList(List<E> list, int fromIndex, int toIndex) { 379 return new SubList<>(list, fromIndex, toIndex - fromIndex); 380 } 381 get(int index)382 public E get(int index) { 383 Objects.checkIndex(index, size); 384 return root.get(offset + index); 385 } 386 size()387 public int size() { 388 return size; 389 } 390 iterator()391 public Iterator<E> iterator() { 392 return new ListItr<>(this, size()); 393 } 394 listIterator(int index)395 public ListIterator<E> listIterator(int index) { 396 rangeCheck(index); 397 return new ListItr<>(this, size(), index); 398 } 399 subList(int fromIndex, int toIndex)400 public List<E> subList(int fromIndex, int toIndex) { 401 subListRangeCheck(fromIndex, toIndex, size); 402 return SubList.fromSubList(this, fromIndex, toIndex); 403 } 404 rangeCheck(int index)405 private void rangeCheck(int index) { 406 if (index < 0 || index > size) { 407 throw outOfBounds(index); 408 } 409 } 410 411 @Override toArray()412 public Object[] toArray() { 413 Object[] array = new Object[size]; 414 for (int i = 0; i < size; i++) { 415 array[i] = get(i); 416 } 417 return array; 418 } 419 420 @Override 421 @SuppressWarnings("unchecked") toArray(T[] a)422 public <T> T[] toArray(T[] a) { 423 T[] array = a.length >= size ? a : 424 (T[])java.lang.reflect.Array 425 .newInstance(a.getClass().getComponentType(), size); 426 for (int i = 0; i < size; i++) { 427 array[i] = (T)get(i); 428 } 429 if (array.length > size) { 430 array[size] = null; // null-terminate 431 } 432 return array; 433 } 434 } 435 436 static final class List12<E> extends AbstractImmutableList<E> 437 implements Serializable { 438 439 @Stable 440 private final E e0; 441 442 @Stable 443 private final Object e1; 444 List12(E e0)445 List12(E e0) { 446 this.e0 = Objects.requireNonNull(e0); 447 // Use EMPTY as a sentinel for an unused element: not using null 448 // enable constant folding optimizations over single-element lists 449 this.e1 = EMPTY; 450 } 451 List12(E e0, E e1)452 List12(E e0, E e1) { 453 this.e0 = Objects.requireNonNull(e0); 454 this.e1 = Objects.requireNonNull(e1); 455 } 456 457 @Override size()458 public int size() { 459 return e1 != EMPTY ? 2 : 1; 460 } 461 462 @Override isEmpty()463 public boolean isEmpty() { 464 return false; 465 } 466 467 @Override 468 @SuppressWarnings("unchecked") get(int index)469 public E get(int index) { 470 if (index == 0) { 471 return e0; 472 } else if (index == 1 && e1 != EMPTY) { 473 return (E)e1; 474 } 475 throw outOfBounds(index); 476 } 477 478 @java.io.Serial readObject(ObjectInputStream in)479 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 480 throw new InvalidObjectException("not serial proxy"); 481 } 482 483 @java.io.Serial writeReplace()484 private Object writeReplace() { 485 if (e1 == EMPTY) { 486 return new CollSer(CollSer.IMM_LIST, e0); 487 } else { 488 return new CollSer(CollSer.IMM_LIST, e0, e1); 489 } 490 } 491 492 @Override toArray()493 public Object[] toArray() { 494 if (e1 == EMPTY) { 495 return new Object[] { e0 }; 496 } else { 497 return new Object[] { e0, e1 }; 498 } 499 } 500 501 @Override 502 @SuppressWarnings("unchecked") toArray(T[] a)503 public <T> T[] toArray(T[] a) { 504 int size = size(); 505 T[] array = a.length >= size ? a : 506 (T[])Array.newInstance(a.getClass().getComponentType(), size); 507 array[0] = (T)e0; 508 if (size == 2) { 509 array[1] = (T)e1; 510 } 511 if (array.length > size) { 512 array[size] = null; // null-terminate 513 } 514 return array; 515 } 516 } 517 518 static final class ListN<E> extends AbstractImmutableList<E> 519 implements Serializable { 520 521 @Stable 522 private final E[] elements; 523 524 @SafeVarargs ListN(E... input)525 ListN(E... input) { 526 // copy and check manually to avoid TOCTOU 527 @SuppressWarnings("unchecked") 528 E[] tmp = (E[])new Object[input.length]; // implicit nullcheck of input 529 for (int i = 0; i < input.length; i++) { 530 tmp[i] = Objects.requireNonNull(input[i]); 531 } 532 elements = tmp; 533 } 534 535 @Override isEmpty()536 public boolean isEmpty() { 537 return elements.length == 0; 538 } 539 540 @Override size()541 public int size() { 542 return elements.length; 543 } 544 545 @Override get(int index)546 public E get(int index) { 547 return elements[index]; 548 } 549 550 @java.io.Serial readObject(ObjectInputStream in)551 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 552 throw new InvalidObjectException("not serial proxy"); 553 } 554 555 @java.io.Serial writeReplace()556 private Object writeReplace() { 557 return new CollSer(CollSer.IMM_LIST, elements); 558 } 559 560 @Override toArray()561 public Object[] toArray() { 562 return Arrays.copyOf(elements, elements.length); 563 } 564 565 @Override 566 @SuppressWarnings("unchecked") toArray(T[] a)567 public <T> T[] toArray(T[] a) { 568 int size = elements.length; 569 if (a.length < size) { 570 // Make a new array of a's runtime type, but my contents: 571 return (T[]) Arrays.copyOf(elements, size, a.getClass()); 572 } 573 System.arraycopy(elements, 0, a, 0, size); 574 if (a.length > size) { 575 a[size] = null; // null-terminate 576 } 577 return a; 578 } 579 } 580 581 // ---------- Set Implementations ---------- 582 583 static abstract class AbstractImmutableSet<E> extends AbstractImmutableCollection<E> 584 implements Set<E> { 585 586 @Override equals(Object o)587 public boolean equals(Object o) { 588 if (o == this) { 589 return true; 590 } else if (!(o instanceof Set)) { 591 return false; 592 } 593 594 Collection<?> c = (Collection<?>) o; 595 if (c.size() != size()) { 596 return false; 597 } 598 for (Object e : c) { 599 if (e == null || !contains(e)) { 600 return false; 601 } 602 } 603 return true; 604 } 605 606 @Override hashCode()607 public abstract int hashCode(); 608 } 609 610 static final class Set12<E> extends AbstractImmutableSet<E> 611 implements Serializable { 612 613 @Stable 614 private final E e0; 615 616 @Stable 617 private final Object e1; 618 Set12(E e0)619 Set12(E e0) { 620 this.e0 = Objects.requireNonNull(e0); 621 // Use EMPTY as a sentinel for an unused element: not using null 622 // enable constant folding optimizations over single-element sets 623 this.e1 = EMPTY; 624 } 625 Set12(E e0, E e1)626 Set12(E e0, E e1) { 627 if (e0.equals(Objects.requireNonNull(e1))) { // implicit nullcheck of e0 628 throw new IllegalArgumentException("duplicate element: " + e0); 629 } 630 631 this.e0 = e0; 632 this.e1 = e1; 633 } 634 635 @Override size()636 public int size() { 637 return (e1 == EMPTY) ? 1 : 2; 638 } 639 640 @Override isEmpty()641 public boolean isEmpty() { 642 return false; 643 } 644 645 @Override contains(Object o)646 public boolean contains(Object o) { 647 return o.equals(e0) || e1.equals(o); // implicit nullcheck of o 648 } 649 650 @Override hashCode()651 public int hashCode() { 652 return e0.hashCode() + (e1 == EMPTY ? 0 : e1.hashCode()); 653 } 654 655 @Override iterator()656 public Iterator<E> iterator() { 657 return new Iterator<>() { 658 private int idx = (e1 == EMPTY) ? 1 : 2; 659 660 @Override 661 public boolean hasNext() { 662 return idx > 0; 663 } 664 665 @Override 666 @SuppressWarnings("unchecked") 667 public E next() { 668 if (idx == 1) { 669 idx = 0; 670 return (REVERSE || e1 == EMPTY) ? e0 : (E)e1; 671 } else if (idx == 2) { 672 idx = 1; 673 return REVERSE ? (E)e1 : e0; 674 } else { 675 throw new NoSuchElementException(); 676 } 677 } 678 }; 679 } 680 681 @java.io.Serial readObject(ObjectInputStream in)682 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 683 throw new InvalidObjectException("not serial proxy"); 684 } 685 686 @java.io.Serial writeReplace()687 private Object writeReplace() { 688 if (e1 == EMPTY) { 689 return new CollSer(CollSer.IMM_SET, e0); 690 } else { 691 return new CollSer(CollSer.IMM_SET, e0, e1); 692 } 693 } 694 695 @Override toArray()696 public Object[] toArray() { 697 if (e1 == EMPTY) { 698 return new Object[] { e0 }; 699 } else if (REVERSE) { 700 return new Object[] { e1, e0 }; 701 } else { 702 return new Object[] { e0, e1 }; 703 } 704 } 705 706 @Override 707 @SuppressWarnings("unchecked") toArray(T[] a)708 public <T> T[] toArray(T[] a) { 709 int size = size(); 710 T[] array = a.length >= size ? a : 711 (T[])Array.newInstance(a.getClass().getComponentType(), size); 712 if (size == 1) { 713 array[0] = (T)e0; 714 } else if (REVERSE) { 715 array[0] = (T)e1; 716 array[1] = (T)e0; 717 } else { 718 array[0] = (T)e0; 719 array[1] = (T)e1; 720 } 721 if (array.length > size) { 722 array[size] = null; // null-terminate 723 } 724 return array; 725 } 726 } 727 728 729 /** 730 * An array-based Set implementation. The element array must be strictly 731 * larger than the size (the number of contained elements) so that at 732 * least one null is always present. 733 * @param <E> the element type 734 */ 735 static final class SetN<E> extends AbstractImmutableSet<E> 736 implements Serializable { 737 738 @Stable 739 final E[] elements; 740 741 @Stable 742 final int size; 743 744 @SafeVarargs 745 @SuppressWarnings("unchecked") SetN(E... input)746 SetN(E... input) { 747 size = input.length; // implicit nullcheck of input 748 749 elements = (E[])new Object[EXPAND_FACTOR * input.length]; 750 for (int i = 0; i < input.length; i++) { 751 E e = input[i]; 752 int idx = probe(e); // implicit nullcheck of e 753 if (idx >= 0) { 754 throw new IllegalArgumentException("duplicate element: " + e); 755 } else { 756 elements[-(idx + 1)] = e; 757 } 758 } 759 } 760 761 @Override size()762 public int size() { 763 return size; 764 } 765 766 @Override isEmpty()767 public boolean isEmpty() { 768 return size == 0; 769 } 770 771 @Override contains(Object o)772 public boolean contains(Object o) { 773 Objects.requireNonNull(o); 774 return size > 0 && probe(o) >= 0; 775 } 776 777 private final class SetNIterator implements Iterator<E> { 778 779 private int remaining; 780 781 private int idx; 782 SetNIterator()783 SetNIterator() { 784 remaining = size; 785 // pick a starting index in the [0 .. element.length-1] range 786 // randomly based on SALT32L 787 idx = (int) ((SALT32L * elements.length) >>> 32); 788 } 789 790 @Override hasNext()791 public boolean hasNext() { 792 return remaining > 0; 793 } 794 795 @Override next()796 public E next() { 797 if (remaining > 0) { 798 E element; 799 int idx = this.idx; 800 int len = elements.length; 801 // step to the next element; skip null elements 802 do { 803 if (REVERSE) { 804 if (++idx >= len) { 805 idx = 0; 806 } 807 } else { 808 if (--idx < 0) { 809 idx = len - 1; 810 } 811 } 812 } while ((element = elements[idx]) == null); 813 this.idx = idx; 814 remaining--; 815 return element; 816 } else { 817 throw new NoSuchElementException(); 818 } 819 } 820 } 821 822 @Override iterator()823 public Iterator<E> iterator() { 824 return new SetNIterator(); 825 } 826 827 @Override hashCode()828 public int hashCode() { 829 int h = 0; 830 for (E e : elements) { 831 if (e != null) { 832 h += e.hashCode(); 833 } 834 } 835 return h; 836 } 837 838 // returns index at which element is present; or if absent, 839 // (-i - 1) where i is location where element should be inserted. 840 // Callers are relying on this method to perform an implicit nullcheck 841 // of pe probe(Object pe)842 private int probe(Object pe) { 843 int idx = Math.floorMod(pe.hashCode(), elements.length); 844 while (true) { 845 E ee = elements[idx]; 846 if (ee == null) { 847 return -idx - 1; 848 } else if (pe.equals(ee)) { 849 return idx; 850 } else if (++idx == elements.length) { 851 idx = 0; 852 } 853 } 854 } 855 856 @java.io.Serial readObject(ObjectInputStream in)857 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 858 throw new InvalidObjectException("not serial proxy"); 859 } 860 861 @java.io.Serial writeReplace()862 private Object writeReplace() { 863 Object[] array = new Object[size]; 864 int dest = 0; 865 for (Object o : elements) { 866 if (o != null) { 867 array[dest++] = o; 868 } 869 } 870 return new CollSer(CollSer.IMM_SET, array); 871 } 872 873 @Override toArray()874 public Object[] toArray() { 875 Object[] array = new Object[size]; 876 Iterator<E> it = iterator(); 877 for (int i = 0; i < size; i++) { 878 array[i] = it.next(); 879 } 880 return array; 881 } 882 883 @Override 884 @SuppressWarnings("unchecked") toArray(T[] a)885 public <T> T[] toArray(T[] a) { 886 T[] array = a.length >= size ? a : 887 (T[])Array.newInstance(a.getClass().getComponentType(), size); 888 Iterator<E> it = iterator(); 889 for (int i = 0; i < size; i++) { 890 array[i] = (T)it.next(); 891 } 892 if (array.length > size) { 893 array[size] = null; // null-terminate 894 } 895 return array; 896 } 897 } 898 899 // ---------- Map Implementations ---------- 900 901 abstract static class AbstractImmutableMap<K,V> extends AbstractMap<K,V> implements Serializable { clear()902 @Override public void clear() { throw uoe(); } compute(K key, BiFunction<? super K,? super V,? extends V> rf)903 @Override public V compute(K key, BiFunction<? super K,? super V,? extends V> rf) { throw uoe(); } computeIfAbsent(K key, Function<? super K,? extends V> mf)904 @Override public V computeIfAbsent(K key, Function<? super K,? extends V> mf) { throw uoe(); } computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> rf)905 @Override public V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> rf) { throw uoe(); } merge(K key, V value, BiFunction<? super V,? super V,? extends V> rf)906 @Override public V merge(K key, V value, BiFunction<? super V,? super V,? extends V> rf) { throw uoe(); } put(K key, V value)907 @Override public V put(K key, V value) { throw uoe(); } putAll(Map<? extends K,? extends V> m)908 @Override public void putAll(Map<? extends K,? extends V> m) { throw uoe(); } putIfAbsent(K key, V value)909 @Override public V putIfAbsent(K key, V value) { throw uoe(); } remove(Object key)910 @Override public V remove(Object key) { throw uoe(); } remove(Object key, Object value)911 @Override public boolean remove(Object key, Object value) { throw uoe(); } replace(K key, V value)912 @Override public V replace(K key, V value) { throw uoe(); } replace(K key, V oldValue, V newValue)913 @Override public boolean replace(K key, V oldValue, V newValue) { throw uoe(); } replaceAll(BiFunction<? super K,? super V,? extends V> f)914 @Override public void replaceAll(BiFunction<? super K,? super V,? extends V> f) { throw uoe(); } 915 916 /** 917 * @implNote {@code null} values are disallowed in these immutable maps, 918 * so we can improve upon the default implementation since a 919 * {@code null} return from {@code get(key)} always means the default 920 * value should be returned. 921 */ 922 @Override getOrDefault(Object key, V defaultValue)923 public V getOrDefault(Object key, V defaultValue) { 924 V v; 925 return ((v = get(key)) != null) 926 ? v 927 : defaultValue; 928 } 929 } 930 931 static final class Map1<K,V> extends AbstractImmutableMap<K,V> { 932 @Stable 933 private final K k0; 934 @Stable 935 private final V v0; 936 Map1(K k0, V v0)937 Map1(K k0, V v0) { 938 this.k0 = Objects.requireNonNull(k0); 939 this.v0 = Objects.requireNonNull(v0); 940 } 941 942 @Override entrySet()943 public Set<Map.Entry<K,V>> entrySet() { 944 return Set.of(new KeyValueHolder<>(k0, v0)); 945 } 946 947 @Override get(Object o)948 public V get(Object o) { 949 return o.equals(k0) ? v0 : null; // implicit nullcheck of o 950 } 951 952 @Override containsKey(Object o)953 public boolean containsKey(Object o) { 954 return o.equals(k0); // implicit nullcheck of o 955 } 956 957 @Override containsValue(Object o)958 public boolean containsValue(Object o) { 959 return o.equals(v0); // implicit nullcheck of o 960 } 961 962 @Override size()963 public int size() { 964 return 1; 965 } 966 967 @Override isEmpty()968 public boolean isEmpty() { 969 return false; 970 } 971 972 @java.io.Serial readObject(ObjectInputStream in)973 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 974 throw new InvalidObjectException("not serial proxy"); 975 } 976 977 @java.io.Serial writeReplace()978 private Object writeReplace() { 979 return new CollSer(CollSer.IMM_MAP, k0, v0); 980 } 981 982 @Override hashCode()983 public int hashCode() { 984 return k0.hashCode() ^ v0.hashCode(); 985 } 986 } 987 988 /** 989 * An array-based Map implementation. There is a single array "table" that 990 * contains keys and values interleaved: table[0] is kA, table[1] is vA, 991 * table[2] is kB, table[3] is vB, etc. The table size must be even. It must 992 * also be strictly larger than the size (the number of key-value pairs contained 993 * in the map) so that at least one null key is always present. 994 * @param <K> the key type 995 * @param <V> the value type 996 */ 997 static final class MapN<K,V> extends AbstractImmutableMap<K,V> { 998 999 @Stable 1000 final Object[] table; // pairs of key, value 1001 1002 @Stable 1003 final int size; // number of pairs 1004 MapN(Object... input)1005 MapN(Object... input) { 1006 if ((input.length & 1) != 0) { // implicit nullcheck of input 1007 throw new InternalError("length is odd"); 1008 } 1009 size = input.length >> 1; 1010 1011 int len = EXPAND_FACTOR * input.length; 1012 len = (len + 1) & ~1; // ensure table is even length 1013 table = new Object[len]; 1014 1015 for (int i = 0; i < input.length; i += 2) { 1016 @SuppressWarnings("unchecked") 1017 K k = Objects.requireNonNull((K)input[i]); 1018 @SuppressWarnings("unchecked") 1019 V v = Objects.requireNonNull((V)input[i+1]); 1020 int idx = probe(k); 1021 if (idx >= 0) { 1022 throw new IllegalArgumentException("duplicate key: " + k); 1023 } else { 1024 int dest = -(idx + 1); 1025 table[dest] = k; 1026 table[dest+1] = v; 1027 } 1028 } 1029 } 1030 1031 @Override containsKey(Object o)1032 public boolean containsKey(Object o) { 1033 Objects.requireNonNull(o); 1034 return size > 0 && probe(o) >= 0; 1035 } 1036 1037 @Override containsValue(Object o)1038 public boolean containsValue(Object o) { 1039 Objects.requireNonNull(o); 1040 for (int i = 1; i < table.length; i += 2) { 1041 Object v = table[i]; 1042 if (v != null && o.equals(v)) { 1043 return true; 1044 } 1045 } 1046 return false; 1047 } 1048 1049 @Override hashCode()1050 public int hashCode() { 1051 int hash = 0; 1052 for (int i = 0; i < table.length; i += 2) { 1053 Object k = table[i]; 1054 if (k != null) { 1055 hash += k.hashCode() ^ table[i + 1].hashCode(); 1056 } 1057 } 1058 return hash; 1059 } 1060 1061 @Override 1062 @SuppressWarnings("unchecked") get(Object o)1063 public V get(Object o) { 1064 if (size == 0) { 1065 Objects.requireNonNull(o); 1066 return null; 1067 } 1068 int i = probe(o); 1069 if (i >= 0) { 1070 return (V)table[i+1]; 1071 } else { 1072 return null; 1073 } 1074 } 1075 1076 @Override size()1077 public int size() { 1078 return size; 1079 } 1080 1081 @Override isEmpty()1082 public boolean isEmpty() { 1083 return size == 0; 1084 } 1085 1086 class MapNIterator implements Iterator<Map.Entry<K,V>> { 1087 1088 private int remaining; 1089 1090 private int idx; 1091 MapNIterator()1092 MapNIterator() { 1093 remaining = size; 1094 // pick an even starting index in the [0 .. table.length-1] 1095 // range randomly based on SALT32L 1096 idx = (int) ((SALT32L * (table.length >> 1)) >>> 32) << 1; 1097 } 1098 1099 @Override hasNext()1100 public boolean hasNext() { 1101 return remaining > 0; 1102 } 1103 nextIndex()1104 private int nextIndex() { 1105 int idx = this.idx; 1106 if (REVERSE) { 1107 if ((idx += 2) >= table.length) { 1108 idx = 0; 1109 } 1110 } else { 1111 if ((idx -= 2) < 0) { 1112 idx = table.length - 2; 1113 } 1114 } 1115 return this.idx = idx; 1116 } 1117 1118 @Override next()1119 public Map.Entry<K,V> next() { 1120 if (remaining > 0) { 1121 int idx; 1122 while (table[idx = nextIndex()] == null) {} 1123 @SuppressWarnings("unchecked") 1124 Map.Entry<K,V> e = 1125 new KeyValueHolder<>((K)table[idx], (V)table[idx+1]); 1126 remaining--; 1127 return e; 1128 } else { 1129 throw new NoSuchElementException(); 1130 } 1131 } 1132 } 1133 1134 @Override entrySet()1135 public Set<Map.Entry<K,V>> entrySet() { 1136 return new AbstractSet<>() { 1137 @Override 1138 public int size() { 1139 return MapN.this.size; 1140 } 1141 1142 @Override 1143 public Iterator<Map.Entry<K,V>> iterator() { 1144 return new MapNIterator(); 1145 } 1146 }; 1147 } 1148 1149 // returns index at which the probe key is present; or if absent, 1150 // (-i - 1) where i is location where element should be inserted. 1151 // Callers are relying on this method to perform an implicit nullcheck 1152 // of pk. 1153 private int probe(Object pk) { 1154 int idx = Math.floorMod(pk.hashCode(), table.length >> 1) << 1; 1155 while (true) { 1156 @SuppressWarnings("unchecked") 1157 K ek = (K)table[idx]; 1158 if (ek == null) { 1159 return -idx - 1; 1160 } else if (pk.equals(ek)) { 1161 return idx; 1162 } else if ((idx += 2) == table.length) { 1163 idx = 0; 1164 } 1165 } 1166 } 1167 1168 @java.io.Serial 1169 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 1170 throw new InvalidObjectException("not serial proxy"); 1171 } 1172 1173 @java.io.Serial 1174 private Object writeReplace() { 1175 Object[] array = new Object[2 * size]; 1176 int len = table.length; 1177 int dest = 0; 1178 for (int i = 0; i < len; i += 2) { 1179 if (table[i] != null) { 1180 array[dest++] = table[i]; 1181 array[dest++] = table[i+1]; 1182 } 1183 } 1184 return new CollSer(CollSer.IMM_MAP, array); 1185 } 1186 } 1187 } 1188 1189 // ---------- Serialization Proxy ---------- 1190 1191 /** 1192 * A unified serialization proxy class for the immutable collections. 1193 * 1194 * @serial 1195 * @since 9 1196 */ 1197 final class CollSer implements Serializable { 1198 @java.io.Serial 1199 private static final long serialVersionUID = 6309168927139932177L; 1200 1201 static final int IMM_LIST = 1; 1202 static final int IMM_SET = 2; 1203 static final int IMM_MAP = 3; 1204 1205 /** 1206 * Indicates the type of collection that is serialized. 1207 * The low order 8 bits have the value 1 for an immutable 1208 * {@code List}, 2 for an immutable {@code Set}, and 3 for 1209 * an immutable {@code Map}. Any other value causes an 1210 * {@link InvalidObjectException} to be thrown. The high 1211 * order 24 bits are zero when an instance is serialized, 1212 * and they are ignored when an instance is deserialized. 1213 * They can thus be used by future implementations without 1214 * causing compatibility issues. 1215 * 1216 * <p>The tag value also determines the interpretation of the 1217 * transient {@code Object[] array} field. 1218 * For {@code List} and {@code Set}, the array's length is the size 1219 * of the collection, and the array contains the elements of the collection. 1220 * Null elements are not allowed. For {@code Set}, duplicate elements 1221 * are not allowed. 1222 * 1223 * <p>For {@code Map}, the array's length is twice the number of mappings 1224 * present in the map. The array length is necessarily even. 1225 * The array contains a succession of key and value pairs: 1226 * {@code k1, v1, k2, v2, ..., kN, vN.} Nulls are not allowed, 1227 * and duplicate keys are not allowed. 1228 * 1229 * @serial 1230 * @since 9 1231 */ 1232 private final int tag; 1233 1234 /** 1235 * @serial 1236 * @since 9 1237 */ 1238 private transient Object[] array; 1239 1240 CollSer(int t, Object... a) { 1241 tag = t; 1242 array = a; 1243 } 1244 1245 /** 1246 * Reads objects from the stream and stores them 1247 * in the transient {@code Object[] array} field. 1248 * 1249 * @serialData 1250 * A nonnegative int, indicating the count of objects, 1251 * followed by that many objects. 1252 * 1253 * @param ois the ObjectInputStream from which data is read 1254 * @throws IOException if an I/O error occurs 1255 * @throws ClassNotFoundException if a serialized class cannot be loaded 1256 * @throws InvalidObjectException if the count is negative 1257 * @since 9 1258 */ 1259 @java.io.Serial 1260 private void readObject(ObjectInputStream ois) throws IOException, ClassNotFoundException { 1261 ois.defaultReadObject(); 1262 int len = ois.readInt(); 1263 1264 if (len < 0) { 1265 throw new InvalidObjectException("negative length " + len); 1266 } 1267 1268 SharedSecrets.getJavaObjectInputStreamAccess().checkArray(ois, Object[].class, len); 1269 Object[] a = new Object[len]; 1270 for (int i = 0; i < len; i++) { 1271 a[i] = ois.readObject(); 1272 } 1273 1274 array = a; 1275 } 1276 1277 /** 1278 * Writes objects to the stream from 1279 * the transient {@code Object[] array} field. 1280 * 1281 * @serialData 1282 * A nonnegative int, indicating the count of objects, 1283 * followed by that many objects. 1284 * 1285 * @param oos the ObjectOutputStream to which data is written 1286 * @throws IOException if an I/O error occurs 1287 * @since 9 1288 */ 1289 @java.io.Serial 1290 private void writeObject(ObjectOutputStream oos) throws IOException { 1291 oos.defaultWriteObject(); 1292 oos.writeInt(array.length); 1293 for (int i = 0; i < array.length; i++) { 1294 oos.writeObject(array[i]); 1295 } 1296 } 1297 1298 /** 1299 * Creates and returns an immutable collection from this proxy class. 1300 * The instance returned is created as if by calling one of the 1301 * static factory methods for 1302 * <a href="List.html#unmodifiable">List</a>, 1303 * <a href="Map.html#unmodifiable">Map</a>, or 1304 * <a href="Set.html#unmodifiable">Set</a>. 1305 * This proxy class is the serial form for all immutable collection instances, 1306 * regardless of implementation type. This is necessary to ensure that the 1307 * existence of any particular implementation type is kept out of the 1308 * serialized form. 1309 * 1310 * @return a collection created from this proxy object 1311 * @throws InvalidObjectException if the tag value is illegal or if an exception 1312 * is thrown during creation of the collection 1313 * @throws ObjectStreamException if another serialization error has occurred 1314 * @since 9 1315 */ 1316 @java.io.Serial 1317 private Object readResolve() throws ObjectStreamException { 1318 try { 1319 if (array == null) { 1320 throw new InvalidObjectException("null array"); 1321 } 1322 1323 // use low order 8 bits to indicate "kind" 1324 // ignore high order 24 bits 1325 switch (tag & 0xff) { 1326 case IMM_LIST: 1327 return List.of(array); 1328 case IMM_SET: 1329 return Set.of(array); 1330 case IMM_MAP: 1331 if (array.length == 0) { 1332 return ImmutableCollections.EMPTY_MAP; 1333 } else if (array.length == 2) { 1334 return new ImmutableCollections.Map1<>(array[0], array[1]); 1335 } else { 1336 return new ImmutableCollections.MapN<>(array); 1337 } 1338 default: 1339 throw new InvalidObjectException(String.format("invalid flags 0x%x", tag)); 1340 } 1341 } catch (NullPointerException|IllegalArgumentException ex) { 1342 InvalidObjectException ioe = new InvalidObjectException("invalid object"); 1343 ioe.initCause(ex); 1344 throw ioe; 1345 } 1346 } 1347 } 1348