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