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