< prev index next >
src/java.base/share/classes/java/util/ImmutableCollections.java
Print this page
rev 49279 : 8193128: Reduce number of implementation classes returned by List/Set/Map.of()
8191418: List.of().indexOf(null) doesn't throw NullPointerException
Reviewed-by: smarks, jrose, martin, plevart
rev 49280 : imported patch reduceclasses_changes
@@ -68,316 +68,408 @@
*/
static final int EXPAND_FACTOR = 2;
static UnsupportedOperationException uoe() { return new UnsupportedOperationException(); }
- // ---------- List Implementations ----------
-
- abstract static class AbstractImmutableList<E> extends AbstractList<E>
- implements RandomAccess, Serializable {
+ static abstract class AbstractImmutableCollection<E> extends AbstractCollection<E> {
+ // all mutating methods throw UnsupportedOperationException
@Override public boolean add(E e) { throw uoe(); }
@Override public boolean addAll(Collection<? extends E> c) { throw uoe(); }
- @Override public boolean addAll(int index, Collection<? extends E> c) { throw uoe(); }
@Override public void clear() { throw uoe(); }
@Override public boolean remove(Object o) { throw uoe(); }
@Override public boolean removeAll(Collection<?> c) { throw uoe(); }
@Override public boolean removeIf(Predicate<? super E> filter) { throw uoe(); }
- @Override public void replaceAll(UnaryOperator<E> operator) { throw uoe(); }
@Override public boolean retainAll(Collection<?> c) { throw uoe(); }
- @Override public void sort(Comparator<? super E> c) { throw uoe(); }
}
- static final class List0<E> extends AbstractImmutableList<E> {
- private static final List0<?> INSTANCE = new List0<>();
+ // ---------- List Implementations ----------
@SuppressWarnings("unchecked")
- static <T> List0<T> instance() {
- return (List0<T>) INSTANCE;
+ static <E> List<E> emptyList() {
+ return (List<E>) ListN.EMPTY_LIST;
}
- private List0() { }
+ static abstract class AbstractImmutableList<E> extends AbstractImmutableCollection<E>
+ implements List<E>, RandomAccess {
+
+ // all mutating methods throw UnsupportedOperationException
+ @Override public void add(int index, E element) { throw uoe(); }
+ @Override public boolean addAll(int index, Collection<? extends E> c) { throw uoe(); }
+ @Override public E remove(int index) { throw uoe(); }
+ @Override public void replaceAll(UnaryOperator<E> operator) { throw uoe(); }
+ @Override public E set(int index, E element) { throw uoe(); }
+ @Override public void sort(Comparator<? super E> c) { throw uoe(); }
@Override
- public int size() {
- return 0;
+ public List<E> subList(int fromIndex, int toIndex) {
+ int size = size();
+ subListRangeCheck(fromIndex, toIndex, size);
+ return SubList.fromList(this, fromIndex, toIndex);
}
- @Override
- public E get(int index) {
- Objects.checkIndex(index, 0); // always throws IndexOutOfBoundsException
- return null; // but the compiler doesn't know this
+ static void subListRangeCheck(int fromIndex, int toIndex, int size) {
+ if (fromIndex < 0)
+ throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
+ if (toIndex > size)
+ throw new IndexOutOfBoundsException("toIndex = " + toIndex);
+ if (fromIndex > toIndex)
+ throw new IllegalArgumentException("fromIndex(" + fromIndex +
+ ") > toIndex(" + toIndex + ")");
}
@Override
public Iterator<E> iterator() {
- return Collections.emptyIterator();
+ return new ListItr<E>(this, size());
}
- private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
- throw new InvalidObjectException("not serial proxy");
+ @Override
+ public ListIterator<E> listIterator() {
+ return listIterator(0);
}
- private Object writeReplace() {
- return new CollSer(CollSer.IMM_LIST);
+ @Override
+ public ListIterator<E> listIterator(final int index) {
+ int size = size();
+ if (index < 0 || index > size) {
+ throw outOfBounds(index);
+ }
+ return new ListItr<E>(this, size, index);
}
@Override
- public boolean contains(Object o) {
- Objects.requireNonNull(o);
- return false;
+ public boolean equals(Object o) {
+ if (o == this) {
+ return true;
}
- @Override
- public boolean containsAll(Collection<?> o) {
- return o.isEmpty(); // implicit nullcheck of o
+ if (!(o instanceof List)) {
+ return false;
}
- @Override
- public int hashCode() {
- return 1;
+ Iterator<?> oit = ((List<?>) o).iterator();
+ for (int i = 0, s = size(); i < s; i++) {
+ if (!oit.hasNext() || !get(i).equals(oit.next())) {
+ return false;
}
}
-
- static final class List1<E> extends AbstractImmutableList<E> {
- @Stable
- private final E e0;
-
- List1(E e0) {
- this.e0 = Objects.requireNonNull(e0);
+ return !oit.hasNext();
}
@Override
- public int size() {
- return 1;
+ public int indexOf(Object o) {
+ Objects.requireNonNull(o);
+ for (int i = 0, s = size(); i < s; i++) {
+ if (o.equals(get(i))) {
+ return i;
+ }
+ }
+ return -1;
}
@Override
- public E get(int index) {
- Objects.checkIndex(index, 1);
- return e0;
+ public int lastIndexOf(Object o) {
+ Objects.requireNonNull(o);
+ for (int i = size() - 1; i >= 0; i--) {
+ if (o.equals(get(i))) {
+ return i;
}
-
- private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
- throw new InvalidObjectException("not serial proxy");
+ }
+ return -1;
}
- private Object writeReplace() {
- return new CollSer(CollSer.IMM_LIST, e0);
+ @Override
+ public int hashCode() {
+ int hash = 1;
+ for (int i = 0, s = size(); i < s; i++) {
+ hash = 31 * hash + get(i).hashCode();
+ }
+ return hash;
}
@Override
public boolean contains(Object o) {
- return o.equals(e0); // implicit nullcheck of o
+ return indexOf(o) >= 0;
}
- @Override
- public int hashCode() {
- return 31 + e0.hashCode();
+ IndexOutOfBoundsException outOfBounds(int index) {
+ return new IndexOutOfBoundsException("Index: " + index + " Size: " + size());
}
}
- static final class List2<E> extends AbstractImmutableList<E> {
+ static final class ListItr<E> implements ListIterator<E> {
+
@Stable
- private final E e0;
+ private final List<E> list;
+
@Stable
- private final E e1;
+ private final int size;
- List2(E e0, E e1) {
- this.e0 = Objects.requireNonNull(e0);
- this.e1 = Objects.requireNonNull(e1);
+ private int cursor;
+
+ ListItr(List<E> list, int size) {
+ this(list, size, 0);
}
- @Override
- public int size() {
- return 2;
+ ListItr(List<E> list, int size, int index) {
+ this.list = list;
+ this.size = size;
+ this.cursor = index;
}
- @Override
- public E get(int index) {
- Objects.checkIndex(index, 2);
- if (index == 0) {
- return e0;
- } else { // index == 1
- return e1;
+ public boolean hasNext() {
+ return cursor != size;
+ }
+
+ public E next() {
+ try {
+ int i = cursor;
+ E next = list.get(i);
+ cursor = i + 1;
+ return next;
+ } catch (IndexOutOfBoundsException e) {
+ throw new NoSuchElementException();
}
}
- @Override
- public boolean contains(Object o) {
- return o.equals(e0) || o.equals(e1); // implicit nullcheck of o
+ public void remove() {
+ throw uoe();
}
- @Override
- public int hashCode() {
- int hash = 31 + e0.hashCode();
- return 31 * hash + e1.hashCode();
+ public boolean hasPrevious() {
+ return cursor != 0;
}
- private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
- throw new InvalidObjectException("not serial proxy");
+ public E previous() {
+ try {
+ int i = cursor - 1;
+ E previous = list.get(i);
+ cursor = i;
+ return previous;
+ } catch (IndexOutOfBoundsException e) {
+ throw new NoSuchElementException();
+ }
}
- private Object writeReplace() {
- return new CollSer(CollSer.IMM_LIST, e0, e1);
+ public int nextIndex() {
+ return cursor;
}
+
+ public int previousIndex() {
+ return cursor - 1;
}
- static final class ListN<E> extends AbstractImmutableList<E> {
- @Stable
- private final E[] elements;
+ public void set(E e) {
+ throw uoe();
+ }
- @SafeVarargs
- ListN(E... input) {
- // copy and check manually to avoid TOCTOU
- @SuppressWarnings("unchecked")
- E[] tmp = (E[])new Object[input.length]; // implicit nullcheck of input
- for (int i = 0; i < input.length; i++) {
- tmp[i] = Objects.requireNonNull(input[i]);
+ public void add(E e) {
+ throw uoe();
}
- this.elements = tmp;
}
- @Override
- public int size() {
- return elements.length;
+ static final class SubList<E> extends AbstractImmutableList<E>
+ implements RandomAccess {
+
+ @Stable
+ private final List<E> root;
+
+ @Stable
+ private final int offset;
+
+ @Stable
+ private final int size;
+
+ private SubList(List<E> root, int offset, int size) {
+ this.root = root;
+ this.offset = offset;
+ this.size = size;
}
- @Override
- public E get(int index) {
- Objects.checkIndex(index, elements.length);
- return elements[index];
+ /**
+ * Constructs a sublist of another SubList.
+ */
+ static <E> SubList<E> fromSubList(SubList<E> parent, int fromIndex, int toIndex) {
+ return new SubList<E>(parent.root, parent.offset + fromIndex, toIndex - fromIndex);
}
- @Override
- public boolean contains(Object o) {
- for (E e : elements) {
- if (o.equals(e)) { // implicit nullcheck of o
- return true;
+ /**
+ * Constructs a sublist of an arbitrary AbstractList, which is
+ * not a SubList itself.
+ */
+ static <E> SubList<E> fromList(List<E> list, int fromIndex, int toIndex) {
+ return new SubList<E>(list, fromIndex, toIndex - fromIndex);
}
+
+ public E get(int index) {
+ Objects.checkIndex(index, size);
+ return root.get(offset + index);
}
- return false;
+
+ public int size() {
+ return size;
}
- @Override
- public int hashCode() {
- int hash = 1;
- for (E e : elements) {
- hash = 31 * hash + e.hashCode();
+ public Iterator<E> iterator() {
+ return new ListItr<E>(this, size());
}
- return hash;
+
+ public ListIterator<E> listIterator(int index) {
+ rangeCheck(index);
+ return new ListItr<E>(this, size(), index);
}
- private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
- throw new InvalidObjectException("not serial proxy");
+ public List<E> subList(int fromIndex, int toIndex) {
+ subListRangeCheck(fromIndex, toIndex, size);
+ return SubList.fromSubList(this, fromIndex, toIndex);
}
- private Object writeReplace() {
- return new CollSer(CollSer.IMM_LIST, elements);
+ private void rangeCheck(int index) {
+ if (index < 0 || index > size) {
+ throw outOfBounds(index);
}
}
-
- // ---------- Set Implementations ----------
-
- abstract static class AbstractImmutableSet<E> extends AbstractSet<E> implements Serializable {
- @Override public boolean add(E e) { throw uoe(); }
- @Override public boolean addAll(Collection<? extends E> c) { throw uoe(); }
- @Override public void clear() { throw uoe(); }
- @Override public boolean remove(Object o) { throw uoe(); }
- @Override public boolean removeAll(Collection<?> c) { throw uoe(); }
- @Override public boolean removeIf(Predicate<? super E> filter) { throw uoe(); }
- @Override public boolean retainAll(Collection<?> c) { throw uoe(); }
}
- static final class Set0<E> extends AbstractImmutableSet<E> {
- private static final Set0<?> INSTANCE = new Set0<>();
+ static final class List12<E> extends AbstractImmutableList<E>
+ implements Serializable {
- @SuppressWarnings("unchecked")
- static <T> Set0<T> instance() {
- return (Set0<T>) INSTANCE;
- }
+ @Stable
+ private final E e0;
- private Set0() { }
+ @Stable
+ private final E e1;
- @Override
- public int size() {
- return 0;
+ List12(E e0) {
+ this.e0 = Objects.requireNonNull(e0);
+ this.e1 = null;
}
- @Override
- public boolean contains(Object o) {
- Objects.requireNonNull(o);
- return false;
+ List12(E e0, E e1) {
+ this.e0 = Objects.requireNonNull(e0);
+ this.e1 = Objects.requireNonNull(e1);
}
@Override
- public boolean containsAll(Collection<?> o) {
- return o.isEmpty(); // implicit nullcheck of o
+ public int size() {
+ return e1 != null ? 2 : 1;
}
@Override
- public Iterator<E> iterator() {
- return Collections.emptyIterator();
+ public E get(int index) {
+ if (index == 0) {
+ return e0;
+ } else if (index == 1 && e1 != null) {
+ return e1;
+ }
+ throw outOfBounds(index);
}
private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
throw new InvalidObjectException("not serial proxy");
}
private Object writeReplace() {
- return new CollSer(CollSer.IMM_SET);
+ if (e1 == null) {
+ return new CollSer(CollSer.IMM_LIST, e0);
+ } else {
+ return new CollSer(CollSer.IMM_LIST, e0, e1);
}
-
- @Override
- public int hashCode() {
- return 0;
}
+
}
- static final class Set1<E> extends AbstractImmutableSet<E> {
+ static final class ListN<E> extends AbstractImmutableList<E>
+ implements Serializable {
+
+ static final List<?> EMPTY_LIST = new ListN<>();
+
@Stable
- private final E e0;
+ private final E[] elements;
- Set1(E e0) {
- this.e0 = Objects.requireNonNull(e0);
+ @SafeVarargs
+ ListN(E... input) {
+ // copy and check manually to avoid TOCTOU
+ @SuppressWarnings("unchecked")
+ E[] tmp = (E[])new Object[input.length]; // implicit nullcheck of input
+ for (int i = 0; i < input.length; i++) {
+ tmp[i] = Objects.requireNonNull(input[i]);
+ }
+ elements = tmp;
}
@Override
- public int size() {
- return 1;
+ public boolean isEmpty() {
+ return size() == 0;
}
@Override
- public boolean contains(Object o) {
- return o.equals(e0); // implicit nullcheck of o
+ public int size() {
+ return elements.length;
}
@Override
- public Iterator<E> iterator() {
- return Collections.singletonIterator(e0);
+ public E get(int index) {
+ return elements[index];
}
private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
throw new InvalidObjectException("not serial proxy");
}
private Object writeReplace() {
- return new CollSer(CollSer.IMM_SET, e0);
+ return new CollSer(CollSer.IMM_LIST, elements);
+ }
}
+ // ---------- Set Implementations ----------
+
+ static abstract class AbstractImmutableSet<E> extends AbstractImmutableCollection<E>
+ implements Set<E> {
+
@Override
- public int hashCode() {
- return e0.hashCode();
+ public boolean equals(Object o) {
+ if (o == this) {
+ return true;
+ } else if (!(o instanceof Set)) {
+ return false;
+ }
+
+ Collection<?> c = (Collection<?>) o;
+ if (c.size() != size()) {
+ return false;
+ }
+ for (Object e : c) {
+ if (e == null || !contains(e)) {
+ return false;
}
}
+ return true;
+ }
+
+ @Override
+ public abstract int hashCode();
+ }
+
+ @SuppressWarnings("unchecked")
+ static <E> Set<E> emptySet() {
+ return (Set<E>) SetN.EMPTY_SET;
+ }
+
+ static final class Set12<E> extends AbstractImmutableSet<E>
+ implements Serializable {
- static final class Set2<E> extends AbstractImmutableSet<E> {
@Stable
final E e0;
@Stable
final E e1;
- Set2(E e0, E e1) {
+ Set12(E e0) {
+ this.e0 = Objects.requireNonNull(e0);
+ this.e1 = null;
+ }
+
+ Set12(E e0, E e1) {
if (e0.equals(Objects.requireNonNull(e1))) { // implicit nullcheck of e0
throw new IllegalArgumentException("duplicate element: " + e0);
}
if (SALT >= 0) {
@@ -389,40 +481,40 @@
}
}
@Override
public int size() {
- return 2;
+ return (e1 == null) ? 1 : 2;
}
@Override
public boolean contains(Object o) {
return o.equals(e0) || o.equals(e1); // implicit nullcheck of o
}
@Override
public int hashCode() {
- return e0.hashCode() + e1.hashCode();
+ return e0.hashCode() + (e1 == null ? 0 : e1.hashCode());
}
@Override
public Iterator<E> iterator() {
- return new Iterator<E>() {
- private int idx = 0;
+ return new Iterator<>() {
+ private int idx = size();
@Override
public boolean hasNext() {
- return idx < 2;
+ return idx > 0;
}
@Override
public E next() {
- if (idx == 0) {
- idx = 1;
+ if (idx == 1) {
+ idx = 0;
return e0;
- } else if (idx == 1) {
- idx = 2;
+ } else if (idx == 2) {
+ idx = 1;
return e1;
} else {
throw new NoSuchElementException();
}
}
@@ -432,21 +524,29 @@
private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
throw new InvalidObjectException("not serial proxy");
}
private Object writeReplace() {
+ if (e1 == null) {
+ return new CollSer(CollSer.IMM_SET, e0);
+ } else {
return new CollSer(CollSer.IMM_SET, e0, e1);
}
}
+ }
/**
* An array-based Set implementation. The element array must be strictly
* larger than the size (the number of contained elements) so that at
* least one null is always present.
* @param <E> the element type
*/
- static final class SetN<E> extends AbstractImmutableSet<E> {
+ static final class SetN<E> extends AbstractImmutableSet<E>
+ implements Serializable {
+
+ static final Set<?> EMPTY_SET = new SetN<>();
+
@Stable
final E[] elements;
@Stable
final int size;
@@ -472,16 +572,17 @@
return size;
}
@Override
public boolean contains(Object o) {
- return probe(o) >= 0; // implicit nullcheck of o
+ Objects.requireNonNull(o);
+ return size > 0 && probe(o) >= 0;
}
@Override
public Iterator<E> iterator() {
- return new Iterator<E>() {
+ return new Iterator<>() {
private int idx = 0;
@Override
public boolean hasNext() {
while (idx < elements.length) {
@@ -547,10 +648,15 @@
}
}
// ---------- Map Implementations ----------
+ @SuppressWarnings("unchecked")
+ static <K,V> Map<K,V> emptyMap() {
+ return (Map<K,V>) MapN.EMPTY_MAP;
+ }
+
abstract static class AbstractImmutableMap<K,V> extends AbstractMap<K,V> implements Serializable {
@Override public void clear() { throw uoe(); }
@Override public V compute(K key, BiFunction<? super K,? super V,? extends V> rf) { throw uoe(); }
@Override public V computeIfAbsent(K key, Function<? super K,? extends V> mf) { throw uoe(); }
@Override public V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> rf) { throw uoe(); }
@@ -563,51 +669,10 @@
@Override public V replace(K key, V value) { throw uoe(); }
@Override public boolean replace(K key, V oldValue, V newValue) { throw uoe(); }
@Override public void replaceAll(BiFunction<? super K,? super V,? extends V> f) { throw uoe(); }
}
- static final class Map0<K,V> extends AbstractImmutableMap<K,V> {
- private static final Map0<?,?> INSTANCE = new Map0<>();
-
- @SuppressWarnings("unchecked")
- static <K,V> Map0<K,V> instance() {
- return (Map0<K,V>) INSTANCE;
- }
-
- private Map0() { }
-
- @Override
- public Set<Map.Entry<K,V>> entrySet() {
- return Set.of();
- }
-
- @Override
- public boolean containsKey(Object o) {
- Objects.requireNonNull(o);
- return false;
- }
-
- @Override
- public boolean containsValue(Object o) {
- Objects.requireNonNull(o);
- return false;
- }
-
- private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
- throw new InvalidObjectException("not serial proxy");
- }
-
- private Object writeReplace() {
- return new CollSer(CollSer.IMM_MAP);
- }
-
- @Override
- public int hashCode() {
- return 0;
- }
- }
-
static final class Map1<K,V> extends AbstractImmutableMap<K,V> {
@Stable
private final K k0;
@Stable
private final V v0;
@@ -654,12 +719,16 @@
* in the map) so that at least one null key is always present.
* @param <K> the key type
* @param <V> the value type
*/
static final class MapN<K,V> extends AbstractImmutableMap<K,V> {
+
+ static final Map<?,?> EMPTY_MAP = new MapN<>();
+
@Stable
final Object[] table; // pairs of key, value
+
@Stable
final int size; // number of pairs
MapN(Object... input) {
if ((input.length & 1) != 0) { // implicit nullcheck of input
@@ -687,18 +756,20 @@
}
}
@Override
public boolean containsKey(Object o) {
- return probe(o) >= 0; // implicit nullcheck of o
+ Objects.requireNonNull(o);
+ return size > 0 && probe(o) >= 0;
}
@Override
public boolean containsValue(Object o) {
+ Objects.requireNonNull(o);
for (int i = 1; i < table.length; i += 2) {
Object v = table[i];
- if (v != null && o.equals(v)) { // implicit nullcheck of o
+ if (v != null && o.equals(v)) {
return true;
}
}
return false;
}
@@ -716,10 +787,14 @@
}
@Override
@SuppressWarnings("unchecked")
public V get(Object o) {
+ if (size == 0) {
+ Objects.requireNonNull(o);
+ return null;
+ }
int i = probe(o);
if (i >= 0) {
return (V)table[i+1];
} else {
return null;
@@ -731,19 +806,19 @@
return size;
}
@Override
public Set<Map.Entry<K,V>> entrySet() {
- return new AbstractSet<Map.Entry<K,V>>() {
+ return new AbstractSet<>() {
@Override
public int size() {
return MapN.this.size;
}
@Override
public Iterator<Map.Entry<K,V>> iterator() {
- return new Iterator<Map.Entry<K,V>>() {
+ return new Iterator<>() {
int idx = 0;
@Override
public boolean hasNext() {
while (idx < table.length) {
@@ -946,11 +1021,11 @@
return List.of(array);
case IMM_SET:
return Set.of(array);
case IMM_MAP:
if (array.length == 0) {
- return ImmutableCollections.Map0.instance();
+ return ImmutableCollections.emptyMap();
} else if (array.length == 2) {
return new ImmutableCollections.Map1<>(array[0], array[1]);
} else {
return new ImmutableCollections.MapN<>(array);
}
< prev index next >