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