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