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 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
422 throw new InvalidObjectException("not serial proxy");
423 }
424
425 private Object writeReplace() {
426 if (e1 == null) {
427 return new CollSer(CollSer.IMM_LIST, e0);
428 } else {
429 return new CollSer(CollSer.IMM_LIST, e0, e1);
430 }
431 }
432
433 @Override
434 public Object[] toArray() {
435 if (e1 == null) {
436 return new Object[] { e0 };
437 } else {
438 return new Object[] { e0, e1 };
439 }
440 }
441
442 @Override
443 @SuppressWarnings("unchecked")
444 public <T> T[] toArray(T[] a) {
445 int size = e1 == null ? 1 : 2;
446 T[] array = a.length >= size ? a :
447 (T[])Array.newInstance(a.getClass().getComponentType(), size);
448 array[0] = (T)e0;
449 if (size == 2) {
450 array[1] = (T)e1;
451 }
452 if (array.length > size) {
453 array[size] = null; // null-terminate
454 }
455 return array;
456 }
457 }
458
459 static final class ListN<E> extends AbstractImmutableList<E>
460 implements Serializable {
461
462 // EMPTY_LIST may be initialized from the CDS archive.
463 static @Stable List<?> EMPTY_LIST;
464
465 static {
466 VM.initializeFromArchive(ListN.class);
467 if (EMPTY_LIST == null) {
468 EMPTY_LIST = new ListN<>();
469 }
470 }
471
472 @Stable
473 private final E[] elements;
474
475 @SafeVarargs
476 ListN(E... input) {
477 // copy and check manually to avoid TOCTOU
478 @SuppressWarnings("unchecked")
479 E[] tmp = (E[])new Object[input.length]; // implicit nullcheck of input
480 for (int i = 0; i < input.length; i++) {
481 tmp[i] = Objects.requireNonNull(input[i]);
482 }
483 elements = tmp;
484 }
485
486 @Override
487 public boolean isEmpty() {
488 return elements.length == 0;
489 }
490
491 @Override
492 public int size() {
493 return elements.length;
494 }
495
496 @Override
497 public E get(int index) {
498 return elements[index];
499 }
500
501 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
502 throw new InvalidObjectException("not serial proxy");
503 }
504
505 private Object writeReplace() {
506 return new CollSer(CollSer.IMM_LIST, elements);
507 }
508
509 @Override
510 public Object[] toArray() {
511 return Arrays.copyOf(elements, elements.length);
512 }
513
514 @Override
515 @SuppressWarnings("unchecked")
516 public <T> T[] toArray(T[] a) {
517 int size = elements.length;
518 if (a.length < size) {
519 // Make a new array of a's runtime type, but my contents:
520 return (T[]) Arrays.copyOf(elements, size, a.getClass());
521 }
522 System.arraycopy(elements, 0, a, 0, size);
523 if (a.length > size) {
524 a[size] = null; // null-terminate
525 }
526 return a;
527 }
528 }
529
530 // ---------- Set Implementations ----------
531
532 static abstract class AbstractImmutableSet<E> extends AbstractImmutableCollection<E>
533 implements Set<E> {
534
535 @Override
536 public boolean equals(Object o) {
537 if (o == this) {
538 return true;
539 } else if (!(o instanceof Set)) {
540 return false;
541 }
542
543 Collection<?> c = (Collection<?>) o;
544 if (c.size() != size()) {
545 return false;
546 }
547 for (Object e : c) {
548 if (e == null || !contains(e)) {
549 return false;
550 }
551 }
552 return true;
553 }
554
555 @Override
556 public abstract int hashCode();
557 }
558
559 static final class Set12<E> extends AbstractImmutableSet<E>
560 implements Serializable {
561
562 @Stable
563 final E e0;
564 @Stable
565 final E e1;
566
567 Set12(E e0) {
568 this.e0 = Objects.requireNonNull(e0);
569 this.e1 = null;
570 }
571
572 Set12(E e0, E e1) {
573 if (e0.equals(Objects.requireNonNull(e1))) { // implicit nullcheck of e0
574 throw new IllegalArgumentException("duplicate element: " + e0);
575 }
576
577 this.e0 = e0;
578 this.e1 = e1;
579 }
580
581 @Override
582 public int size() {
583 return (e1 == null) ? 1 : 2;
584 }
585
586 @Override
587 public boolean isEmpty() {
588 return false;
589 }
590
591 @Override
592 public boolean contains(Object o) {
593 return o.equals(e0) || o.equals(e1); // implicit nullcheck of o
594 }
595
596 @Override
597 public int hashCode() {
598 return e0.hashCode() + (e1 == null ? 0 : e1.hashCode());
599 }
600
601 @Override
602 public Iterator<E> iterator() {
603 return new Iterator<>() {
604 private int idx = size();
605
606 @Override
607 public boolean hasNext() {
608 return idx > 0;
609 }
610
611 @Override
612 public E next() {
613 if (idx == 1) {
614 idx = 0;
615 return SALT >= 0 || e1 == null ? e0 : e1;
616 } else if (idx == 2) {
617 idx = 1;
618 return SALT >= 0 ? e1 : e0;
619 } else {
620 throw new NoSuchElementException();
621 }
622 }
623 };
624 }
625
626 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
627 throw new InvalidObjectException("not serial proxy");
628 }
629
630 private Object writeReplace() {
631 if (e1 == null) {
632 return new CollSer(CollSer.IMM_SET, e0);
633 } else {
634 return new CollSer(CollSer.IMM_SET, e0, e1);
635 }
636 }
637
638 @Override
639 public Object[] toArray() {
640 if (e1 == null) {
641 return new Object[] { e0 };
642 } else if (SALT >= 0) {
643 return new Object[] { e1, e0 };
644 } else {
645 return new Object[] { e0, e1 };
646 }
647 }
648
649 @Override
650 @SuppressWarnings("unchecked")
651 public <T> T[] toArray(T[] a) {
652 int size = e1 == null ? 1 : 2;
653 T[] array = a.length >= size ? a :
654 (T[])Array.newInstance(a.getClass().getComponentType(), size);
655 if (size == 1) {
656 array[0] = (T)e0;
657 } else if (SALT >= 0) {
658 array[0] = (T)e1;
659 array[1] = (T)e0;
660 } else {
661 array[0] = (T)e0;
662 array[1] = (T)e1;
663 }
664 if (array.length > size) {
665 array[size] = null; // null-terminate
666 }
667 return array;
668 }
669 }
670
671
672 /**
673 * An array-based Set implementation. The element array must be strictly
674 * larger than the size (the number of contained elements) so that at
675 * least one null is always present.
676 * @param <E> the element type
677 */
678 static final class SetN<E> extends AbstractImmutableSet<E>
679 implements Serializable {
680
681 // EMPTY_SET may be initialized from the CDS archive.
682 static @Stable Set<?> EMPTY_SET;
683
684 static {
685 VM.initializeFromArchive(SetN.class);
686 if (EMPTY_SET == null) {
687 EMPTY_SET = new SetN<>();
688 }
689 }
690
691 @Stable
692 final E[] elements;
693 @Stable
694 final int size;
695
696 @SafeVarargs
697 @SuppressWarnings("unchecked")
698 SetN(E... input) {
699 size = input.length; // implicit nullcheck of input
700
701 elements = (E[])new Object[EXPAND_FACTOR * input.length];
702 for (int i = 0; i < input.length; i++) {
703 E e = input[i];
704 int idx = probe(e); // implicit nullcheck of e
705 if (idx >= 0) {
706 throw new IllegalArgumentException("duplicate element: " + e);
707 } else {
708 elements[-(idx + 1)] = e;
709 }
710 }
711 }
712
713 @Override
714 public int size() {
715 return size;
716 }
717
718 @Override
719 public boolean isEmpty() {
720 return size == 0;
721 }
722
723 @Override
724 public boolean contains(Object o) {
725 Objects.requireNonNull(o);
726 return size > 0 && probe(o) >= 0;
727 }
728
729 private final class SetNIterator implements Iterator<E> {
730
731 private int remaining;
732
733 private int idx;
734
735 SetNIterator() {
736 remaining = size();
737 if (remaining > 0) {
738 idx = Math.floorMod(SALT, elements.length);
739 }
740 }
741
742 @Override
743 public boolean hasNext() {
744 return remaining > 0;
745 }
746
747 private int nextIndex() {
748 int idx = this.idx;
749 if (SALT >= 0) {
750 if (++idx >= elements.length) {
751 idx = 0;
752 }
753 } else {
754 if (--idx < 0) {
755 idx = elements.length - 1;
756 }
757 }
758 return this.idx = idx;
759 }
760
761 @Override
762 public E next() {
763 if (remaining > 0) {
764 E element;
765 // skip null elements
766 while ((element = elements[nextIndex()]) == null) {}
767 remaining--;
768 return element;
769 } else {
770 throw new NoSuchElementException();
771 }
772 }
773 }
774
775 @Override
776 public Iterator<E> iterator() {
777 return new SetNIterator();
778 }
779
780 @Override
781 public int hashCode() {
782 int h = 0;
783 for (E e : elements) {
784 if (e != null) {
785 h += e.hashCode();
786 }
787 }
788 return h;
789 }
790
791 // returns index at which element is present; or if absent,
792 // (-i - 1) where i is location where element should be inserted.
793 // Callers are relying on this method to perform an implicit nullcheck
794 // of pe
795 private int probe(Object pe) {
796 int idx = Math.floorMod(pe.hashCode(), elements.length);
797 while (true) {
798 E ee = elements[idx];
799 if (ee == null) {
800 return -idx - 1;
801 } else if (pe.equals(ee)) {
802 return idx;
803 } else if (++idx == elements.length) {
804 idx = 0;
805 }
806 }
807 }
808
809 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
810 throw new InvalidObjectException("not serial proxy");
811 }
812
813 private Object writeReplace() {
814 Object[] array = new Object[size];
815 int dest = 0;
816 for (Object o : elements) {
817 if (o != null) {
818 array[dest++] = o;
819 }
820 }
821 return new CollSer(CollSer.IMM_SET, array);
822 }
823
824 @Override
825 public Object[] toArray() {
826 Object[] array = new Object[size];
827 Iterator<E> it = iterator();
828 for (int i = 0; i < size; i++) {
829 array[i] = it.next();
830 }
831 return array;
832 }
833
834 @Override
835 @SuppressWarnings("unchecked")
836 public <T> T[] toArray(T[] a) {
837 T[] array = a.length >= size ? a :
838 (T[])Array.newInstance(a.getClass().getComponentType(), size);
839 Iterator<E> it = iterator();
840 for (int i = 0; i < size; i++) {
841 array[i] = (T)it.next();
842 }
843 if (array.length > size) {
844 array[size] = null; // null-terminate
845 }
846 return array;
847 }
848 }
849
850 // ---------- Map Implementations ----------
851
852 abstract static class AbstractImmutableMap<K,V> extends AbstractMap<K,V> implements Serializable {
853 @Override public void clear() { throw uoe(); }
854 @Override public V compute(K key, BiFunction<? super K,? super V,? extends V> rf) { throw uoe(); }
855 @Override public V computeIfAbsent(K key, Function<? super K,? extends V> mf) { throw uoe(); }
856 @Override public V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> rf) { throw uoe(); }
857 @Override public V merge(K key, V value, BiFunction<? super V,? super V,? extends V> rf) { throw uoe(); }
858 @Override public V put(K key, V value) { throw uoe(); }
859 @Override public void putAll(Map<? extends K,? extends V> m) { throw uoe(); }
860 @Override public V putIfAbsent(K key, V value) { throw uoe(); }
861 @Override public V remove(Object key) { throw uoe(); }
862 @Override public boolean remove(Object key, Object value) { throw uoe(); }
863 @Override public V replace(K key, V value) { throw uoe(); }
864 @Override public boolean replace(K key, V oldValue, V newValue) { throw uoe(); }
865 @Override public void replaceAll(BiFunction<? super K,? super V,? extends V> f) { throw uoe(); }
866 }
867
868 static final class Map1<K,V> extends AbstractImmutableMap<K,V> {
869 @Stable
870 private final K k0;
871 @Stable
872 private final V v0;
873
874 Map1(K k0, V v0) {
875 this.k0 = Objects.requireNonNull(k0);
876 this.v0 = Objects.requireNonNull(v0);
877 }
878
879 @Override
880 public Set<Map.Entry<K,V>> entrySet() {
881 return Set.of(new KeyValueHolder<>(k0, v0));
882 }
883
884 @Override
885 public V get(Object o) {
886 return o.equals(k0) ? v0 : null; // implicit nullcheck of o
887 }
888
889 @Override
890 public boolean containsKey(Object o) {
891 return o.equals(k0); // implicit nullcheck of o
892 }
893
894 @Override
895 public boolean containsValue(Object o) {
896 return o.equals(v0); // implicit nullcheck of o
897 }
898
899 @Override
900 public int size() {
901 return 1;
902 }
903
904 @Override
905 public boolean isEmpty() {
906 return false;
907 }
908
909 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
910 throw new InvalidObjectException("not serial proxy");
911 }
912
913 private Object writeReplace() {
914 return new CollSer(CollSer.IMM_MAP, k0, v0);
915 }
916
917 @Override
918 public int hashCode() {
919 return k0.hashCode() ^ v0.hashCode();
920 }
921 }
922
923 /**
924 * An array-based Map implementation. There is a single array "table" that
925 * contains keys and values interleaved: table[0] is kA, table[1] is vA,
926 * table[2] is kB, table[3] is vB, etc. The table size must be even. It must
927 * also be strictly larger than the size (the number of key-value pairs contained
928 * in the map) so that at least one null key is always present.
929 * @param <K> the key type
930 * @param <V> the value type
931 */
932 static final class MapN<K,V> extends AbstractImmutableMap<K,V> {
933
934 // EMPTY_MAP may be initialized from the CDS archive.
935 static @Stable Map<?,?> EMPTY_MAP;
936
937 static {
938 VM.initializeFromArchive(MapN.class);
939 if (EMPTY_MAP == null) {
940 EMPTY_MAP = new MapN<>();
941 }
942 }
943
944 @Stable
945 final Object[] table; // pairs of key, value
946
947 @Stable
948 final int size; // number of pairs
949
950 MapN(Object... input) {
951 if ((input.length & 1) != 0) { // implicit nullcheck of input
952 throw new InternalError("length is odd");
953 }
954 size = input.length >> 1;
955
956 int len = EXPAND_FACTOR * input.length;
957 len = (len + 1) & ~1; // ensure table is even length
958 table = new Object[len];
959
960 for (int i = 0; i < input.length; i += 2) {
961 @SuppressWarnings("unchecked")
962 K k = Objects.requireNonNull((K)input[i]);
963 @SuppressWarnings("unchecked")
964 V v = Objects.requireNonNull((V)input[i+1]);
965 int idx = probe(k);
966 if (idx >= 0) {
967 throw new IllegalArgumentException("duplicate key: " + k);
968 } else {
969 int dest = -(idx + 1);
970 table[dest] = k;
971 table[dest+1] = v;
972 }
973 }
974 }
975
976 @Override
977 public boolean containsKey(Object o) {
978 Objects.requireNonNull(o);
979 return size > 0 && probe(o) >= 0;
980 }
981
982 @Override
983 public boolean containsValue(Object o) {
984 Objects.requireNonNull(o);
985 for (int i = 1; i < table.length; i += 2) {
986 Object v = table[i];
987 if (v != null && o.equals(v)) {
988 return true;
989 }
990 }
991 return false;
992 }
993
994 @Override
995 public int hashCode() {
996 int hash = 0;
997 for (int i = 0; i < table.length; i += 2) {
998 Object k = table[i];
999 if (k != null) {
1000 hash += k.hashCode() ^ table[i + 1].hashCode();
1001 }
1002 }
1003 return hash;
1004 }
1005
1006 @Override
1007 @SuppressWarnings("unchecked")
1008 public V get(Object o) {
1009 if (size == 0) {
1010 Objects.requireNonNull(o);
1011 return null;
1012 }
1013 int i = probe(o);
1014 if (i >= 0) {
1015 return (V)table[i+1];
1016 } else {
1017 return null;
1018 }
1019 }
1020
1021 @Override
1022 public int size() {
1023 return size;
1024 }
1025
1026 @Override
1027 public boolean isEmpty() {
1028 return size == 0;
1029 }
1030
1031 class MapNIterator implements Iterator<Map.Entry<K,V>> {
1032
1033 private int remaining;
1034
1035 private int idx;
1036
1037 MapNIterator() {
1038 remaining = size();
1039 if (remaining > 0) {
1040 idx = Math.floorMod(SALT, table.length >> 1) << 1;
1041 }
1042 }
1043
1044 @Override
1045 public boolean hasNext() {
1046 return remaining > 0;
1047 }
1048
1049 private int nextIndex() {
1050 int idx = this.idx;
1051 if (SALT >= 0) {
1052 if ((idx += 2) >= table.length) {
1053 idx = 0;
1054 }
1055 } else {
1056 if ((idx -= 2) < 0) {
1057 idx = table.length - 2;
1058 }
1059 }
1060 return this.idx = idx;
1061 }
1062
1063 @Override
1064 public Map.Entry<K,V> next() {
1065 if (remaining > 0) {
1066 int idx;
1067 while (table[idx = nextIndex()] == null) {}
1068 @SuppressWarnings("unchecked")
1069 Map.Entry<K,V> e =
1070 new KeyValueHolder<>((K)table[idx], (V)table[idx+1]);
1071 remaining--;
1072 return e;
1073 } else {
1074 throw new NoSuchElementException();
1075 }
1076 }
1077 }
1078
1079 @Override
1080 public Set<Map.Entry<K,V>> entrySet() {
1081 return new AbstractSet<>() {
1082 @Override
1083 public int size() {
1084 return MapN.this.size;
1085 }
1086
1087 @Override
1088 public Iterator<Map.Entry<K,V>> iterator() {
1089 return new MapNIterator();
1090 }
1091 };
1092 }
1093
1094 // returns index at which the probe key is present; or if absent,
1095 // (-i - 1) where i is location where element should be inserted.
1096 // Callers are relying on this method to perform an implicit nullcheck
1097 // of pk.
1098 private int probe(Object pk) {
1099 int idx = Math.floorMod(pk.hashCode(), table.length >> 1) << 1;
1100 while (true) {
1101 @SuppressWarnings("unchecked")
1102 K ek = (K)table[idx];
1103 if (ek == null) {
1104 return -idx - 1;
1105 } else if (pk.equals(ek)) {
1106 return idx;
1107 } else if ((idx += 2) == table.length) {
1108 idx = 0;
1109 }
1110 }
1111 }
1112
1113 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
1114 throw new InvalidObjectException("not serial proxy");
1115 }
1116
1117 private Object writeReplace() {
1118 Object[] array = new Object[2 * size];
1119 int len = table.length;
1120 int dest = 0;
1121 for (int i = 0; i < len; i += 2) {
1122 if (table[i] != null) {
1123 array[dest++] = table[i];
1124 array[dest++] = table[i+1];
1125 }
1126 }
1127 return new CollSer(CollSer.IMM_MAP, array);
1128 }
1129 }
1130 }
1131
1132 // ---------- Serialization Proxy ----------
1133
1134 /**
1135 * A unified serialization proxy class for the immutable collections.
1136 *
1137 * @serial
1138 * @since 9
1139 */
1140 final class CollSer implements Serializable {
1141 private static final long serialVersionUID = 6309168927139932177L;
1142
1143 static final int IMM_LIST = 1;
1144 static final int IMM_SET = 2;
1145 static final int IMM_MAP = 3;
1146
1147 /**
1148 * Indicates the type of collection that is serialized.
1149 * The low order 8 bits have the value 1 for an immutable
1150 * {@code List}, 2 for an immutable {@code Set}, and 3 for
1151 * an immutable {@code Map}. Any other value causes an
1152 * {@link InvalidObjectException} to be thrown. The high
1153 * order 24 bits are zero when an instance is serialized,
1154 * and they are ignored when an instance is deserialized.
1155 * They can thus be used by future implementations without
1156 * causing compatibility issues.
1157 *
1158 * <p>The tag value also determines the interpretation of the
1159 * transient {@code Object[] array} field.
1160 * For {@code List} and {@code Set}, the array's length is the size
1161 * of the collection, and the array contains the elements of the collection.
1162 * Null elements are not allowed. For {@code Set}, duplicate elements
1163 * are not allowed.
1164 *
1165 * <p>For {@code Map}, the array's length is twice the number of mappings
1166 * present in the map. The array length is necessarily even.
1167 * The array contains a succession of key and value pairs:
1168 * {@code k1, v1, k2, v2, ..., kN, vN.} Nulls are not allowed,
1169 * and duplicate keys are not allowed.
1170 *
1171 * @serial
1172 * @since 9
1173 */
1174 private final int tag;
1175
1176 /**
1177 * @serial
1178 * @since 9
1179 */
1180 private transient Object[] array;
1181
1182 CollSer(int t, Object... a) {
1183 tag = t;
1184 array = a;
1185 }
1186
1187 /**
1188 * Reads objects from the stream and stores them
1189 * in the transient {@code Object[] array} field.
1190 *
1191 * @serialData
1192 * A nonnegative int, indicating the count of objects,
1193 * followed by that many objects.
1194 *
1195 * @param ois the ObjectInputStream from which data is read
1196 * @throws IOException if an I/O error occurs
1197 * @throws ClassNotFoundException if a serialized class cannot be loaded
1198 * @throws InvalidObjectException if the count is negative
1199 * @since 9
1200 */
1201 private void readObject(ObjectInputStream ois) throws IOException, ClassNotFoundException {
1202 ois.defaultReadObject();
1203 int len = ois.readInt();
1204
1205 if (len < 0) {
1206 throw new InvalidObjectException("negative length " + len);
1207 }
1208
1209 SharedSecrets.getJavaObjectInputStreamAccess().checkArray(ois, Object[].class, len);
1210 Object[] a = new Object[len];
1211 for (int i = 0; i < len; i++) {
1212 a[i] = ois.readObject();
1213 }
1214
1215 array = a;
1216 }
1217
1218 /**
1219 * Writes objects to the stream from
1220 * the transient {@code Object[] array} field.
1221 *
1222 * @serialData
1223 * A nonnegative int, indicating the count of objects,
1224 * followed by that many objects.
1225 *
1226 * @param oos the ObjectOutputStream to which data is written
1227 * @throws IOException if an I/O error occurs
1228 * @since 9
1229 */
1230 private void writeObject(ObjectOutputStream oos) throws IOException {
1231 oos.defaultWriteObject();
1232 oos.writeInt(array.length);
1233 for (int i = 0; i < array.length; i++) {
1234 oos.writeObject(array[i]);
1235 }
1236 }
1237
1238 /**
1239 * Creates and returns an immutable collection from this proxy class.
1240 * The instance returned is created as if by calling one of the
1241 * static factory methods for
1242 * <a href="List.html#unmodifiable">List</a>,
1243 * <a href="Map.html#unmodifiable">Map</a>, or
1244 * <a href="Set.html#unmodifiable">Set</a>.
1245 * This proxy class is the serial form for all immutable collection instances,
1246 * regardless of implementation type. This is necessary to ensure that the
1247 * existence of any particular implementation type is kept out of the
1248 * serialized form.
1249 *
1250 * @return a collection created from this proxy object
1251 * @throws InvalidObjectException if the tag value is illegal or if an exception
1252 * is thrown during creation of the collection
1253 * @throws ObjectStreamException if another serialization error has occurred
1254 * @since 9
1255 */
1256 private Object readResolve() throws ObjectStreamException {
1257 try {
1258 if (array == null) {
1259 throw new InvalidObjectException("null array");
1260 }
1261
1262 // use low order 8 bits to indicate "kind"
1263 // ignore high order 24 bits
1264 switch (tag & 0xff) {
1265 case IMM_LIST:
1266 return List.of(array);
1267 case IMM_SET:
1268 return Set.of(array);
1269 case IMM_MAP:
1270 if (array.length == 0) {
1271 return ImmutableCollections.MapN.EMPTY_MAP;
1272 } else if (array.length == 2) {
1273 return new ImmutableCollections.Map1<>(array[0], array[1]);
1274 } else {
1275 return new ImmutableCollections.MapN<>(array);
1276 }
1277 default:
1278 throw new InvalidObjectException(String.format("invalid flags 0x%x", tag));
1279 }
1280 } catch (NullPointerException|IllegalArgumentException ex) {
1281 InvalidObjectException ioe = new InvalidObjectException("invalid object");
1282 ioe.initCause(ex);
1283 throw ioe;
1284 }
1285 }
1286 }