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