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