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