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