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