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