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