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