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