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