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