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