< prev index next >

src/java.base/share/classes/java/util/ImmutableCollections.java

Print this page
rev 48077 : 8193128: Reduce number of implementation classes returned by List/Set/Map.of()
Reviewed-by: smarks


  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     abstract static class AbstractImmutableList<E> extends AbstractList<E>
  76                                                 implements RandomAccess, Serializable {









  77         @Override public boolean add(E e) { throw uoe(); }

  78         @Override public boolean addAll(Collection<? extends E> c) { throw uoe(); }
  79         @Override public boolean addAll(int index, Collection<? extends E> c) { throw uoe(); }
  80         @Override public void    clear() { throw uoe(); }
  81         @Override public boolean remove(Object o) { throw uoe(); }

  82         @Override public boolean removeAll(Collection<?> c) { throw uoe(); }
  83         @Override public boolean removeIf(Predicate<? super E> filter) { throw uoe(); }
  84         @Override public void    replaceAll(UnaryOperator<E> operator) { throw uoe(); }
  85         @Override public boolean retainAll(Collection<?> c) { throw uoe(); }

  86         @Override public void    sort(Comparator<? super E> c) { throw uoe(); }




  87     }
  88 
  89     static final class List0<E> extends AbstractImmutableList<E> {
  90         private static final List0<?> INSTANCE = new List0<>();




  91 
  92         @SuppressWarnings("unchecked")
  93         static <T> List0<T> instance() {
  94             return (List0<T>) INSTANCE;










  95         }
  96 
  97         private List0() { }












  98 
  99         @Override
 100         public int size() {
 101             return 0;

















































 102         }
 103 
 104         @Override
 105         public E get(int index) {
 106             Objects.checkIndex(index, 0); // always throws IndexOutOfBoundsException
 107             return null;                  // but the compiler doesn't know this









 108         }
 109 
 110         @Override
 111         public Iterator<E> iterator() {
 112             return Collections.emptyIterator();


 113         }
 114 
 115         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
 116             throw new InvalidObjectException("not serial proxy");





 117         }
 118 
 119         private Object writeReplace() {
 120             return new CollSer(CollSer.IMM_LIST);


















 121         }
 122 
 123         @Override
 124         public boolean contains(Object o) {
 125             Objects.requireNonNull(o);
 126             return false;
 127         }
 128 
 129         @Override
 130         public boolean containsAll(Collection<?> o) {
 131             return o.isEmpty(); // implicit nullcheck of o
 132         }
 133 
 134         @Override
 135         public int hashCode() {
 136             return 1;


 137         }

 138     }
 139 
 140     static final class List1<E> extends AbstractImmutableList<E> {
 141         @Stable
 142         private final E e0;
 143 
 144         List1(E e0) {
 145             this.e0 = Objects.requireNonNull(e0);




 146         }
 147 
 148         @Override
 149         public int size() {
 150             return 1;
 151         }
 152 
 153         @Override
 154         public E get(int index) {
 155             Objects.checkIndex(index, 1);
 156             return e0;





 157         }
 158 
 159         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
 160             throw new InvalidObjectException("not serial proxy");

 161         }
 162 
 163         private Object writeReplace() {
 164             return new CollSer(CollSer.IMM_LIST, e0);



 165         }
 166 
 167         @Override
 168         public boolean contains(Object o) {
 169             return o.equals(e0); // implicit nullcheck of o


















 170         }
 171 










 172         @Override
 173         public int hashCode() {
 174             return 31 + e0.hashCode();





















 175         }
 176     }
 177 
 178     static final class List2<E> extends AbstractImmutableList<E> {

 179         @Stable
 180         private final E e0;

 181         @Stable
 182         private final E e1;
 183 
 184         List2(E e0, E e1) {





 185             this.e0 = Objects.requireNonNull(e0);
 186             this.e1 = Objects.requireNonNull(e1);
 187         }
 188 
 189         @Override
 190         public int size() {
 191             return 2;
 192         }
 193 
 194         @Override
 195         public E get(int index) {
 196             Objects.checkIndex(index, 2);
 197             if (index == 0) {
 198                 return e0;
 199             } else { // index == 1
 200                 return e1;
 201             }

 202         }
 203 
 204         @Override
 205         public boolean contains(Object o) {
 206             return o.equals(e0) || o.equals(e1); // implicit nullcheck of o
 207         }
 208 
 209         @Override
 210         public int hashCode() {
 211             int hash = 31 + e0.hashCode();
 212             return 31 * hash + e1.hashCode();



 213         }
 214 
 215         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
 216             throw new InvalidObjectException("not serial proxy");
 217         }
 218 
 219         private Object writeReplace() {



 220             return new CollSer(CollSer.IMM_LIST, e0, e1);
 221         }
 222     }
 223 
 224     static final class ListN<E> extends AbstractImmutableList<E> {



































 225         @Stable
 226         private final E[] elements;
 227 










 228         @SafeVarargs
 229         ListN(E... input) {
 230             // copy and check manually to avoid TOCTOU
 231             @SuppressWarnings("unchecked")
 232             E[] tmp = (E[])new Object[input.length]; // implicit nullcheck of input
 233             for (int i = 0; i < input.length; i++) {
 234                 tmp[i] = Objects.requireNonNull(input[i]);
 235             }
 236             this.elements = tmp;





 237         }
 238 
 239         @Override
 240         public int size() {
 241             return elements.length;
 242         }
 243 
 244         @Override
 245         public E get(int index) {
 246             Objects.checkIndex(index, elements.length);
 247             return elements[index];
 248         }
 249 
 250         @Override
 251         public boolean contains(Object o) {

 252             for (E e : elements) {
 253                 if (o.equals(e)) { // implicit nullcheck of o
 254                     return true;
 255                 }
 256             }
 257             return false;
 258         }
 259 
 260         @Override
 261         public int hashCode() {
 262             int hash = 1;
 263             for (E e : elements) {
 264                 hash = 31 * hash + e.hashCode();
 265             }
 266             return hash;
 267         }
 268 
 269         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
 270             throw new InvalidObjectException("not serial proxy");



 271         }
 272 
 273         private Object writeReplace() {
 274             return new CollSer(CollSer.IMM_LIST, elements);

 275         }
 276     }
 277 
 278     // ---------- Set Implementations ----------
 279 
 280     abstract static class AbstractImmutableSet<E> extends AbstractSet<E> implements Serializable {
 281         @Override public boolean add(E e) { throw uoe(); }
 282         @Override public boolean addAll(Collection<? extends E> c) { throw uoe(); }
 283         @Override public void    clear() { throw uoe(); }
 284         @Override public boolean remove(Object o) { throw uoe(); }
 285         @Override public boolean removeAll(Collection<?> c) { throw uoe(); }
 286         @Override public boolean removeIf(Predicate<? super E> filter) { throw uoe(); }
 287         @Override public boolean retainAll(Collection<?> c) { throw uoe(); }
 288     }
 289 
 290     static final class Set0<E> extends AbstractImmutableSet<E> {
 291         private static final Set0<?> INSTANCE = new Set0<>();
 292 
 293         @SuppressWarnings("unchecked")
 294         static <T> Set0<T> instance() {
 295             return (Set0<T>) INSTANCE;
 296         }
 297 
 298         private Set0() { }
 299 
 300         @Override
 301         public int size() {
 302             return 0;


 303         }
 304 
 305         @Override
 306         public boolean contains(Object o) {
 307             Objects.requireNonNull(o);
 308             return false;
 309         }
 310 
 311         @Override
 312         public boolean containsAll(Collection<?> o) {
 313             return o.isEmpty(); // implicit nullcheck of o
 314         }
 315 
 316         @Override
 317         public Iterator<E> iterator() {
 318             return Collections.emptyIterator();
 319         }
 320 
 321         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
 322             throw new InvalidObjectException("not serial proxy");
 323         }
 324 
 325         private Object writeReplace() {
 326             return new CollSer(CollSer.IMM_SET);
 327         }
 328 
 329         @Override
 330         public int hashCode() {
 331             return 0;
 332         }
 333     }
 334 
 335     static final class Set1<E> extends AbstractImmutableSet<E> {
 336         @Stable
 337         private final E e0;
 338 
 339         Set1(E e0) {
 340             this.e0 = Objects.requireNonNull(e0);
 341         }
 342 
 343         @Override
 344         public int size() {
 345             return 1;
 346         }
 347 
 348         @Override
 349         public boolean contains(Object o) {
 350             return o.equals(e0); // implicit nullcheck of o
 351         }
 352 
 353         @Override
 354         public Iterator<E> iterator() {
 355             return Collections.singletonIterator(e0);
 356         }
 357 
 358         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
 359             throw new InvalidObjectException("not serial proxy");
 360         }
 361 
 362         private Object writeReplace() {
 363             return new CollSer(CollSer.IMM_SET, e0);

 364         }
 365 
 366         @Override
 367         public int hashCode() {
 368             return e0.hashCode();
 369         }




 370     }
 371 
 372     static final class Set2<E> extends AbstractImmutableSet<E> {
 373         @Stable
 374         final E e0;
 375         @Stable
 376         final E e1;
 377 
 378         Set2(E e0, E e1) {





 379             if (e0.equals(Objects.requireNonNull(e1))) { // implicit nullcheck of e0
 380                 throw new IllegalArgumentException("duplicate element: " + e0);
 381             }
 382 
 383             if (SALT >= 0) {
 384                 this.e0 = e0;
 385                 this.e1 = e1;
 386             } else {
 387                 this.e0 = e1;
 388                 this.e1 = e0;
 389             }
 390         }
 391 
 392         @Override
 393         public int size() {
 394             return 2;
 395         }
 396 
 397         @Override
 398         public boolean contains(Object o) {
 399             return o.equals(e0) || o.equals(e1); // implicit nullcheck of o
 400         }
 401 
 402         @Override
 403         public int hashCode() {
 404             return e0.hashCode() + e1.hashCode();
 405         }
 406 
 407         @Override
 408         public Iterator<E> iterator() {
 409             return new Iterator<E>() {
 410                 private int idx = 0;
 411 
 412                 @Override
 413                 public boolean hasNext() {
 414                     return idx < 2;
 415                 }
 416 
 417                 @Override
 418                 public E next() {
 419                     if (idx == 0) {
 420                         idx = 1;
 421                         return e0;
 422                     } else if (idx == 1) {
 423                         idx = 2;
 424                         return e1;
 425                     } else {
 426                         throw new NoSuchElementException();
 427                     }
 428                 }
 429             };
 430         }
 431 
 432         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
 433             throw new InvalidObjectException("not serial proxy");
 434         }
 435 
 436         private Object writeReplace() {



 437             return new CollSer(CollSer.IMM_SET, e0, e1);
 438         }
 439     }

 440 
 441     /**
 442      * An array-based Set implementation. The element array must be strictly
 443      * larger than the size (the number of contained elements) so that at
 444      * least one null is always present.
 445      * @param <E> the element type
 446      */
 447     static final class SetN<E> extends AbstractImmutableSet<E> {
 448         @Stable
 449         final E[] elements;
 450         @Stable
 451         final int size;
 452 
 453         @SafeVarargs
 454         @SuppressWarnings("unchecked")
 455         SetN(E... input) {
 456             size = input.length; // implicit nullcheck of input
 457 
 458             elements = (E[])new Object[EXPAND_FACTOR * input.length];
 459             for (int i = 0; i < input.length; i++) {
 460                 E e = input[i];
 461                 int idx = probe(e); // implicit nullcheck of e
 462                 if (idx >= 0) {
 463                     throw new IllegalArgumentException("duplicate element: " + e);
 464                 } else {
 465                     elements[-(idx + 1)] = e;
 466                 }
 467             }
 468         }
 469 
 470         @Override
 471         public int size() {
 472             return size;
 473         }
 474 
 475         @Override
 476         public boolean contains(Object o) {
 477             return probe(o) >= 0; // implicit nullcheck of o

 478         }
 479 
 480         @Override
 481         public Iterator<E> iterator() {
 482             return new Iterator<E>() {
 483                 private int idx = 0;
 484 
 485                 @Override
 486                 public boolean hasNext() {
 487                     while (idx < elements.length) {
 488                         if (elements[idx] != null)
 489                             return true;
 490                         idx++;
 491                     }
 492                     return false;
 493                 }
 494 
 495                 @Override
 496                 public E next() {
 497                     if (! hasNext()) {


 532         }
 533 
 534         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
 535             throw new InvalidObjectException("not serial proxy");
 536         }
 537 
 538         private Object writeReplace() {
 539             Object[] array = new Object[size];
 540             int dest = 0;
 541             for (Object o : elements) {
 542                 if (o != null) {
 543                     array[dest++] = o;
 544                 }
 545             }
 546             return new CollSer(CollSer.IMM_SET, array);
 547         }
 548     }
 549 
 550     // ---------- Map Implementations ----------
 551 







 552     abstract static class AbstractImmutableMap<K,V> extends AbstractMap<K,V> implements Serializable {
 553         @Override public void clear() { throw uoe(); }
 554         @Override public V compute(K key, BiFunction<? super K,? super V,? extends V> rf) { throw uoe(); }
 555         @Override public V computeIfAbsent(K key, Function<? super K,? extends V> mf) { throw uoe(); }
 556         @Override public V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> rf) { throw uoe(); }
 557         @Override public V merge(K key, V value, BiFunction<? super V,? super V,? extends V> rf) { throw uoe(); }
 558         @Override public V put(K key, V value) { throw uoe(); }
 559         @Override public void putAll(Map<? extends K,? extends V> m) { throw uoe(); }
 560         @Override public V putIfAbsent(K key, V value) { throw uoe(); }
 561         @Override public V remove(Object key) { throw uoe(); }
 562         @Override public boolean remove(Object key, Object value) { throw uoe(); }
 563         @Override public V replace(K key, V value) { throw uoe(); }
 564         @Override public boolean replace(K key, V oldValue, V newValue) { throw uoe(); }
 565         @Override public void replaceAll(BiFunction<? super K,? super V,? extends V> f) { throw uoe(); }
 566     }
 567 
 568     static final class Map0<K,V> extends AbstractImmutableMap<K,V> {
 569         private static final Map0<?,?> INSTANCE = new Map0<>();
 570 
 571         @SuppressWarnings("unchecked")
 572         static <K,V> Map0<K,V> instance() {
 573             return (Map0<K,V>) INSTANCE;
 574         }
 575 
 576         private Map0() { }
 577 
 578         @Override
 579         public Set<Map.Entry<K,V>> entrySet() {
 580             return Set.of();
 581         }
 582 
 583         @Override
 584         public boolean containsKey(Object o) {
 585             Objects.requireNonNull(o);
 586             return false;
 587         }
 588 
 589         @Override
 590         public boolean containsValue(Object o) {
 591             Objects.requireNonNull(o);
 592             return false;
 593         }
 594 
 595         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
 596             throw new InvalidObjectException("not serial proxy");
 597         }
 598 
 599         private Object writeReplace() {
 600             return new CollSer(CollSer.IMM_MAP);
 601         }
 602 
 603         @Override
 604         public int hashCode() {
 605             return 0;
 606         }
 607     }
 608 
 609     static final class Map1<K,V> extends AbstractImmutableMap<K,V> {
 610         @Stable
 611         private final K k0;
 612         @Stable
 613         private final V v0;
 614 
 615         Map1(K k0, V v0) {
 616             this.k0 = Objects.requireNonNull(k0);
 617             this.v0 = Objects.requireNonNull(v0);
 618         }
 619 
 620         @Override
 621         public Set<Map.Entry<K,V>> entrySet() {
 622             return Set.of(new KeyValueHolder<>(k0, v0));
 623         }
 624 
 625         @Override
 626         public boolean containsKey(Object o) {
 627             return o.equals(k0); // implicit nullcheck of o
 628         }


 641         }
 642 
 643         @Override
 644         public int hashCode() {
 645             return k0.hashCode() ^ v0.hashCode();
 646         }
 647     }
 648 
 649     /**
 650      * An array-based Map implementation. There is a single array "table" that
 651      * contains keys and values interleaved: table[0] is kA, table[1] is vA,
 652      * table[2] is kB, table[3] is vB, etc. The table size must be even. It must
 653      * also be strictly larger than the size (the number of key-value pairs contained
 654      * in the map) so that at least one null key is always present.
 655      * @param <K> the key type
 656      * @param <V> the value type
 657      */
 658     static final class MapN<K,V> extends AbstractImmutableMap<K,V> {
 659         @Stable
 660         final Object[] table; // pairs of key, value

 661         @Stable
 662         final int size; // number of pairs
 663 
 664         MapN(Object... input) {
 665             if ((input.length & 1) != 0) { // implicit nullcheck of input
 666                 throw new InternalError("length is odd");
 667             }
 668             size = input.length >> 1;
 669 
 670             int len = EXPAND_FACTOR * input.length;
 671             len = (len + 1) & ~1; // ensure table is even length
 672             table = new Object[len];
 673 
 674             for (int i = 0; i < input.length; i += 2) {
 675                 @SuppressWarnings("unchecked")
 676                     K k = Objects.requireNonNull((K)input[i]);
 677                 @SuppressWarnings("unchecked")
 678                     V v = Objects.requireNonNull((V)input[i+1]);
 679                 int idx = probe(k);
 680                 if (idx >= 0) {
 681                     throw new IllegalArgumentException("duplicate key: " + k);
 682                 } else {
 683                     int dest = -(idx + 1);
 684                     table[dest] = k;
 685                     table[dest+1] = v;
 686                 }
 687             }
 688         }
 689 
 690         @Override
 691         public boolean containsKey(Object o) {
 692             return probe(o) >= 0; // implicit nullcheck of o

 693         }
 694 
 695         @Override
 696         public boolean containsValue(Object o) {
 697             for (int i = 1; i < table.length; i += 2) {
 698                 Object v = table[i];
 699                 if (v != null && o.equals(v)) { // implicit nullcheck of o
 700                     return true;
 701                 }
 702             }
 703             return false;
 704         }
 705 
 706         @Override
 707         public int hashCode() {
 708             int hash = 0;
 709             for (int i = 0; i < table.length; i += 2) {
 710                 Object k = table[i];
 711                 if (k != null) {
 712                     hash += k.hashCode() ^ table[i + 1].hashCode();
 713                 }
 714             }
 715             return hash;
 716         }
 717 
 718         @Override
 719         @SuppressWarnings("unchecked")
 720         public V get(Object o) {



 721             int i = probe(o);
 722             if (i >= 0) {
 723                 return (V)table[i+1];
 724             } else {
 725                 return null;
 726             }
 727         }
 728 
 729         @Override
 730         public int size() {
 731             return size;
 732         }
 733 
 734         @Override
 735         public Set<Map.Entry<K,V>> entrySet() {
 736             return new AbstractSet<Map.Entry<K,V>>() {
 737                 @Override
 738                 public int size() {
 739                     return MapN.this.size;
 740                 }


 931      * @throws InvalidObjectException if the tag value is illegal or if an exception
 932      *         is thrown during creation of the collection
 933      * @throws ObjectStreamException if another serialization error has occurred
 934      * @since 9
 935      */
 936     private Object readResolve() throws ObjectStreamException {
 937         try {
 938             if (array == null) {
 939                 throw new InvalidObjectException("null array");
 940             }
 941 
 942             // use low order 8 bits to indicate "kind"
 943             // ignore high order 24 bits
 944             switch (tag & 0xff) {
 945                 case IMM_LIST:
 946                     return List.of(array);
 947                 case IMM_SET:
 948                     return Set.of(array);
 949                 case IMM_MAP:
 950                     if (array.length == 0) {
 951                         return ImmutableCollections.Map0.instance();
 952                     } else if (array.length == 2) {
 953                         return new ImmutableCollections.Map1<>(array[0], array[1]);
 954                     } else {
 955                         return new ImmutableCollections.MapN<>(array);
 956                     }
 957                 default:
 958                     throw new InvalidObjectException(String.format("invalid flags 0x%x", tag));
 959             }
 960         } catch (NullPointerException|IllegalArgumentException ex) {
 961             InvalidObjectException ioe = new InvalidObjectException("invalid object");
 962             ioe.initCause(ex);
 963             throw ioe;
 964         }
 965     }
 966 }


  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()) {


 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         }


 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                 }


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 }
< prev index next >