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