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