8166365: Small immutable collections should provide optimized implementations when possible
Reviewed-by: smarks, psandoz, attila
--- a/jdk/src/java.base/share/classes/java/util/Collections.java Thu Jan 12 11:41:51 2017 +0000
+++ b/jdk/src/java.base/share/classes/java/util/Collections.java Thu Jan 12 13:38:27 2017 +0100
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 1997, 2016, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1997, 2017, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -4354,6 +4354,11 @@
private Object readResolve() {
return EMPTY_SET;
}
+
+ @Override
+ public int hashCode() {
+ return 0;
+ }
}
/**
@@ -4786,6 +4791,10 @@
public boolean removeIf(Predicate<? super E> filter) {
throw new UnsupportedOperationException();
}
+ @Override
+ public int hashCode() {
+ return Objects.hashCode(element);
+ }
}
/**
@@ -4848,6 +4857,10 @@
public Spliterator<E> spliterator() {
return singletonSpliterator(element);
}
+ @Override
+ public int hashCode() {
+ return Objects.hashCode(element);
+ }
}
/**
@@ -4970,6 +4983,11 @@
BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
throw new UnsupportedOperationException();
}
+
+ @Override
+ public int hashCode() {
+ return Objects.hashCode(k) ^ Objects.hashCode(v);
+ }
}
// Miscellaneous
--- a/jdk/src/java.base/share/classes/java/util/ImmutableCollections.java Thu Jan 12 11:41:51 2017 +0000
+++ b/jdk/src/java.base/share/classes/java/util/ImmutableCollections.java Thu Jan 12 13:38:27 2017 +0100
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2016, 2017, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -35,6 +35,7 @@
import java.util.function.Function;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
+import jdk.internal.vm.annotation.Stable;
/**
* Container class for immutable collections. Not part of the public API.
@@ -105,6 +106,11 @@
return null; // but the compiler doesn't know this
}
+ @Override
+ public Iterator<E> iterator() {
+ return Collections.emptyIterator();
+ }
+
private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
throw new InvalidObjectException("not serial proxy");
}
@@ -112,9 +118,26 @@
private Object writeReplace() {
return new CollSer(CollSer.IMM_LIST);
}
+
+ @Override
+ public boolean contains(Object o) {
+ Objects.requireNonNull(o);
+ return false;
+ }
+
+ @Override
+ public boolean containsAll(Collection<?> o) {
+ return o.isEmpty(); // implicit nullcheck of o
+ }
+
+ @Override
+ public int hashCode() {
+ return 1;
+ }
}
static final class List1<E> extends AbstractImmutableList<E> {
+ @Stable
private final E e0;
List1(E e0) {
@@ -129,7 +152,6 @@
@Override
public E get(int index) {
Objects.checkIndex(index, 1);
- // assert index == 0
return e0;
}
@@ -140,10 +162,22 @@
private Object writeReplace() {
return new CollSer(CollSer.IMM_LIST, e0);
}
+
+ @Override
+ public boolean contains(Object o) {
+ return o.equals(e0); // implicit nullcheck of o
+ }
+
+ @Override
+ public int hashCode() {
+ return 31 + e0.hashCode();
+ }
}
static final class List2<E> extends AbstractImmutableList<E> {
+ @Stable
private final E e0;
+ @Stable
private final E e1;
List2(E e0, E e1) {
@@ -166,6 +200,17 @@
}
}
+ @Override
+ public boolean contains(Object o) {
+ return o.equals(e0) || o.equals(e1); // implicit nullcheck of o
+ }
+
+ @Override
+ public int hashCode() {
+ int hash = 31 + e0.hashCode();
+ return 31 * hash + e1.hashCode();
+ }
+
private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
throw new InvalidObjectException("not serial proxy");
}
@@ -176,6 +221,7 @@
}
static final class ListN<E> extends AbstractImmutableList<E> {
+ @Stable
private final E[] elements;
@SafeVarargs
@@ -200,6 +246,25 @@
return elements[index];
}
+ @Override
+ public boolean contains(Object o) {
+ for (E e : elements) {
+ if (o.equals(e)) { // implicit nullcheck of o
+ return true;
+ }
+ }
+ return false;
+ }
+
+ @Override
+ public int hashCode() {
+ int hash = 1;
+ for (E e : elements) {
+ hash = 31 * hash + e.hashCode();
+ }
+ return hash;
+ }
+
private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
throw new InvalidObjectException("not serial proxy");
}
@@ -238,7 +303,13 @@
@Override
public boolean contains(Object o) {
- return super.contains(Objects.requireNonNull(o));
+ Objects.requireNonNull(o);
+ return false;
+ }
+
+ @Override
+ public boolean containsAll(Collection<?> o) {
+ return o.isEmpty(); // implicit nullcheck of o
}
@Override
@@ -253,9 +324,15 @@
private Object writeReplace() {
return new CollSer(CollSer.IMM_SET);
}
+
+ @Override
+ public int hashCode() {
+ return 0;
+ }
}
static final class Set1<E> extends AbstractImmutableSet<E> {
+ @Stable
private final E e0;
Set1(E e0) {
@@ -269,7 +346,7 @@
@Override
public boolean contains(Object o) {
- return super.contains(Objects.requireNonNull(o));
+ return o.equals(e0); // implicit nullcheck of o
}
@Override
@@ -284,17 +361,21 @@
private Object writeReplace() {
return new CollSer(CollSer.IMM_SET, e0);
}
+
+ @Override
+ public int hashCode() {
+ return e0.hashCode();
+ }
}
static final class Set2<E> extends AbstractImmutableSet<E> {
- private final E e0;
- private final E e1;
+ @Stable
+ final E e0;
+ @Stable
+ final E e1;
Set2(E e0, E e1) {
- Objects.requireNonNull(e0);
- Objects.requireNonNull(e1);
-
- if (e0.equals(e1)) {
+ if (e0.equals(Objects.requireNonNull(e1))) { // implicit nullcheck of e0
throw new IllegalArgumentException("duplicate element: " + e0);
}
@@ -314,7 +395,12 @@
@Override
public boolean contains(Object o) {
- return super.contains(Objects.requireNonNull(o));
+ return o.equals(e0) || o.equals(e1); // implicit nullcheck of o
+ }
+
+ @Override
+ public int hashCode() {
+ return e0.hashCode() + e1.hashCode();
}
@Override
@@ -358,8 +444,10 @@
* @param <E> the element type
*/
static final class SetN<E> extends AbstractImmutableSet<E> {
- private final E[] elements;
- private final int size;
+ @Stable
+ final E[] elements;
+ @Stable
+ final int size;
@SafeVarargs
@SuppressWarnings("unchecked")
@@ -368,8 +456,8 @@
elements = (E[])new Object[EXPAND_FACTOR * input.length];
for (int i = 0; i < input.length; i++) {
- E e = Objects.requireNonNull(input[i]);
- int idx = probe(e);
+ E e = input[i];
+ int idx = probe(e); // implicit nullcheck of e
if (idx >= 0) {
throw new IllegalArgumentException("duplicate element: " + e);
} else {
@@ -385,8 +473,7 @@
@Override
public boolean contains(Object o) {
- Objects.requireNonNull(o);
- return probe(o) >= 0;
+ return probe(o) >= 0; // implicit nullcheck of o
}
@Override
@@ -414,8 +501,21 @@
};
}
+ @Override
+ public int hashCode() {
+ int h = 0;
+ for (E e : elements) {
+ if (e != null) {
+ h += e.hashCode();
+ }
+ }
+ return h;
+ }
+
// returns index at which element is present; or if absent,
- // (-i - 1) where i is location where element should be inserted
+ // (-i - 1) where i is location where element should be inserted.
+ // Callers are relying on this method to perform an implicit nullcheck
+ // of pe
private int probe(Object pe) {
int idx = Math.floorMod(pe.hashCode() ^ SALT, elements.length);
while (true) {
@@ -481,12 +581,14 @@
@Override
public boolean containsKey(Object o) {
- return super.containsKey(Objects.requireNonNull(o));
+ Objects.requireNonNull(o);
+ return false;
}
@Override
public boolean containsValue(Object o) {
- return super.containsValue(Objects.requireNonNull(o));
+ Objects.requireNonNull(o);
+ return false;
}
private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
@@ -496,10 +598,17 @@
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;
Map1(K k0, V v0) {
@@ -514,12 +623,12 @@
@Override
public boolean containsKey(Object o) {
- return super.containsKey(Objects.requireNonNull(o));
+ return o.equals(k0); // implicit nullcheck of o
}
@Override
public boolean containsValue(Object o) {
- return super.containsValue(Objects.requireNonNull(o));
+ return o.equals(v0); // implicit nullcheck of o
}
private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
@@ -529,6 +638,11 @@
private Object writeReplace() {
return new CollSer(CollSer.IMM_MAP, k0, v0);
}
+
+ @Override
+ public int hashCode() {
+ return k0.hashCode() ^ v0.hashCode();
+ }
}
/**
@@ -541,12 +655,13 @@
* @param <V> the value type
*/
static final class MapN<K,V> extends AbstractImmutableMap<K,V> {
- private final Object[] table; // pairs of key, value
- private final int size; // number of pairs
+ @Stable
+ final Object[] table; // pairs of key, value
+ @Stable
+ final int size; // number of pairs
MapN(Object... input) {
- Objects.requireNonNull(input);
- if ((input.length & 1) != 0) {
+ if ((input.length & 1) != 0) { // implicit nullcheck of input
throw new InternalError("length is odd");
}
size = input.length >> 1;
@@ -573,12 +688,30 @@
@Override
public boolean containsKey(Object o) {
- return probe(Objects.requireNonNull(o)) >= 0;
+ return probe(o) >= 0; // implicit nullcheck of o
}
@Override
public boolean containsValue(Object o) {
- return super.containsValue(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
+ return true;
+ }
+ }
+ return false;
+ }
+
+ @Override
+ public int hashCode() {
+ int hash = 0;
+ for (int i = 0; i < table.length; i += 2) {
+ Object k = table[i];
+ if (k != null) {
+ hash += k.hashCode() ^ table[i + 1].hashCode();
+ }
+ }
+ return hash;
}
@Override
@@ -638,7 +771,9 @@
}
// returns index at which the probe key is present; or if absent,
- // (-i - 1) where i is location where element should be inserted
+ // (-i - 1) where i is location where element should be inserted.
+ // Callers are relying on this method to perform an implicit nullcheck
+ // of pk.
private int probe(Object pk) {
int idx = Math.floorMod(pk.hashCode() ^ SALT, table.length >> 1) << 1;
while (true) {
--- a/jdk/src/java.base/share/classes/java/util/KeyValueHolder.java Thu Jan 12 11:41:51 2017 +0000
+++ b/jdk/src/java.base/share/classes/java/util/KeyValueHolder.java Thu Jan 12 13:38:27 2017 +0100
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2015, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2015, 2017, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -25,6 +25,8 @@
package java.util;
+import jdk.internal.vm.annotation.Stable;
+
/**
* An immutable container for a key and a value, suitable for use
* in creating and populating {@code Map} instances.
@@ -48,7 +50,9 @@
* @since 9
*/
final class KeyValueHolder<K,V> implements Map.Entry<K,V> {
+ @Stable
final K key;
+ @Stable
final V value;
KeyValueHolder(K k, V v) {
--- a/jdk/src/java.base/share/classes/java/util/List.java Thu Jan 12 11:41:51 2017 +0000
+++ b/jdk/src/java.base/share/classes/java/util/List.java Thu Jan 12 13:38:27 2017 +0100
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 1997, 2016, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1997, 2017, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -1027,8 +1027,7 @@
@SafeVarargs
@SuppressWarnings("varargs")
static <E> List<E> of(E... elements) {
- Objects.requireNonNull(elements);
- switch (elements.length) {
+ switch (elements.length) { // implicit null check of elements
case 0:
return ImmutableCollections.List0.instance();
case 1:
--- a/jdk/src/java.base/share/classes/java/util/Map.java Thu Jan 12 11:41:51 2017 +0000
+++ b/jdk/src/java.base/share/classes/java/util/Map.java Thu Jan 12 13:38:27 2017 +0100
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 1997, 2016, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1997, 2017, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -1602,8 +1602,7 @@
@SafeVarargs
@SuppressWarnings("varargs")
static <K, V> Map<K, V> ofEntries(Entry<? extends K, ? extends V>... entries) {
- Objects.requireNonNull(entries);
- if (entries.length == 0) {
+ if (entries.length == 0) { // implicit null check of entries
return ImmutableCollections.Map0.instance();
} else if (entries.length == 1) {
return new ImmutableCollections.Map1<>(entries[0].getKey(),
--- a/jdk/src/java.base/share/classes/java/util/Set.java Thu Jan 12 11:41:51 2017 +0000
+++ b/jdk/src/java.base/share/classes/java/util/Set.java Thu Jan 12 13:38:27 2017 +0100
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 1997, 2016, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1997, 2017, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -689,8 +689,7 @@
@SafeVarargs
@SuppressWarnings("varargs")
static <E> Set<E> of(E... elements) {
- Objects.requireNonNull(elements);
- switch (elements.length) {
+ switch (elements.length) { // implicit null check of elements
case 0:
return ImmutableCollections.Set0.instance();
case 1:
--- a/jdk/test/java/util/Collection/SetFactories.java Thu Jan 12 11:41:51 2017 +0000
+++ b/jdk/test/java/util/Collection/SetFactories.java Thu Jan 12 13:38:27 2017 +0100
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2015, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2015, 2017, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -103,6 +103,8 @@
hashSetOf("a", "b", "c", "d", "e", "f", "g", "h", "i")),
a( Set.of("a", "b", "c", "d", "e", "f", "g", "h", "i", "j"),
hashSetOf("a", "b", "c", "d", "e", "f", "g", "h", "i", "j")),
+ a( Set.of("a", "b", "c", "d", "e", "f", "g", "h", "i", "j"),
+ Set.of("j", "i", "h", "g", "f", "e", "d", "c", "b", "a")),
a( Set.of(stringArray),
hashSetOf(stringArray))
).iterator();
@@ -183,6 +185,17 @@
Set<String> set = Set.of(array);
}
+ @Test(dataProvider="all")
+ public void hashCodeEqual(Set<String> act, Set<String> exp) {
+ assertEquals(act.hashCode(), exp.hashCode());
+ }
+
+ @Test(dataProvider="all")
+ public void containsAll(Set<String> act, Set<String> exp) {
+ assertTrue(act.containsAll(exp));
+ assertTrue(exp.containsAll(act));
+ }
+
@Test(expectedExceptions=NullPointerException.class)
public void nullDisallowed1() {
Set.of((String)null); // force one-arg overload
--- a/jdk/test/java/util/Map/MapFactories.java Thu Jan 12 11:41:51 2017 +0000
+++ b/jdk/test/java/util/Map/MapFactories.java Thu Jan 12 13:38:27 2017 +0100
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2015, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2015, 2017, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -103,6 +103,8 @@
a(Map.of(0, "a", 1, "b", 2, "c", 3, "d", 4, "e", 5, "f", 6, "g", 7, "h"), genMap(8)),
a(Map.of(0, "a", 1, "b", 2, "c", 3, "d", 4, "e", 5, "f", 6, "g", 7, "h", 8, "i"), genMap(9)),
a(Map.of(0, "a", 1, "b", 2, "c", 3, "d", 4, "e", 5, "f", 6, "g", 7, "h", 8, "i", 9, "j"), genMap(10)),
+ a(Map.of(0, "a", 1, "b", 2, "c", 3, "d", 4, "e", 5, "f", 6, "g", 7, "h", 8, "i", 9, "j"),
+ Map.of(4, "e", 5, "f", 6, "g", 7, "h", 8, "i", 9, "j", 0, "a", 1, "b", 2, "c", 3, "d")),
a(Map.ofEntries(genEntries(MAX_ENTRIES)), genMap(MAX_ENTRIES))
).iterator();
}
@@ -135,6 +137,18 @@
assertEquals(act, exp);
}
+ @Test(dataProvider="all")
+ public void containsAllKeys(Map<Integer,String> act, Map<Integer,String> exp) {
+ assertTrue(act.keySet().containsAll(exp.keySet()));
+ assertTrue(exp.keySet().containsAll(act.keySet()));
+ }
+
+ @Test(dataProvider="all")
+ public void containsAllValues(Map<Integer,String> act, Map<Integer,String> exp) {
+ assertTrue(act.values().containsAll(exp.values()));
+ assertTrue(exp.values().containsAll(act.values()));
+ }
+
@Test(expectedExceptions=IllegalArgumentException.class)
public void dupKeysDisallowed2() {
Map<Integer, String> map = Map.of(0, "a", 0, "b");
@@ -192,6 +206,11 @@
Map<Integer, String> map = Map.ofEntries(entries);
}
+ @Test(dataProvider="all")
+ public void hashCodeEquals(Map<Integer,String> act, Map<Integer,String> exp) {
+ assertEquals(act.hashCode(), exp.hashCode());
+ }
+
@Test(expectedExceptions=NullPointerException.class)
public void nullKeyDisallowed1() {
Map<Integer, String> map = Map.of(null, "a");