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