8139233: add initial compact immutable collection implementations
Reviewed-by: plevart, forax, dfuchs, chegar, alanb, scolebourne
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/src/java.base/share/classes/java/util/ImmutableCollections.java Fri May 06 11:33:32 2016 -0700
@@ -0,0 +1,657 @@
+/*
+ * Copyright (c) 2016, 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
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation. Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+package java.util;
+
+import java.io.IOException;
+import java.io.InvalidObjectException;
+import java.io.ObjectInputStream;
+import java.io.ObjectStreamException;
+import java.io.Serializable;
+
+/**
+ * Container class for immutable collections. Not part of the public API.
+ * Mainly for namespace management and shared infrastructure.
+ *
+ * Serial warnings are suppressed throughout because all implementation
+ * classes use a serial proxy and thus have no need to declare serialVersionUID.
+ */
+@SuppressWarnings("serial")
+class ImmutableCollections {
+ /**
+ * A "salt" value used for randomizing iteration order. This is initialized once
+ * and stays constant for the lifetime of the JVM. It need not be truly random, but
+ * it needs to vary sufficiently from one run to the next so that iteration order
+ * will vary between JVM runs.
+ */
+ static final int SALT;
+ static {
+ SALT = new Random().nextInt();
+ }
+
+ /** No instances. */
+ private ImmutableCollections() { }
+
+ /**
+ * The reciprocal of load factor. Given a number of elements
+ * to store, multiply by this factor to get the table size.
+ */
+ static final double EXPAND_FACTOR = 2.0;
+
+ // ---------- List Implementations ----------
+
+ static final class List0<E> extends AbstractList<E> implements RandomAccess, Serializable {
+ List0() { }
+
+ @Override
+ public int size() {
+ return 0;
+ }
+
+ @Override
+ public E get(int index) {
+ Objects.checkIndex(index, 0); // always throws IndexOutOfBoundsException
+ return null; // but the compiler doesn't know this
+ }
+
+ private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+ throw new InvalidObjectException("not serial proxy");
+ }
+
+ private Object writeReplace() {
+ return new CollSer(CollSer.IMM_LIST);
+ }
+ }
+
+ static final class List1<E> extends AbstractList<E> implements RandomAccess, Serializable {
+ private final E e0;
+
+ List1(E e0) {
+ this.e0 = Objects.requireNonNull(e0);
+ }
+
+ @Override
+ public int size() {
+ return 1;
+ }
+
+ @Override
+ public E get(int index) {
+ Objects.checkIndex(index, 1);
+ // assert index == 0
+ return e0;
+ }
+
+ private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+ throw new InvalidObjectException("not serial proxy");
+ }
+
+ private Object writeReplace() {
+ return new CollSer(CollSer.IMM_LIST, e0);
+ }
+ }
+
+ static final class List2<E> extends AbstractList<E> implements RandomAccess, Serializable {
+ private final E e0;
+ private final E e1;
+
+ List2(E e0, E e1) {
+ this.e0 = Objects.requireNonNull(e0);
+ this.e1 = Objects.requireNonNull(e1);
+ }
+
+ @Override
+ public int size() {
+ return 2;
+ }
+
+ @Override
+ public E get(int index) {
+ Objects.checkIndex(index, 2);
+ if (index == 0) {
+ return e0;
+ } else { // index == 1
+ return e1;
+ }
+ }
+
+ private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+ throw new InvalidObjectException("not serial proxy");
+ }
+
+ private Object writeReplace() {
+ return new CollSer(CollSer.IMM_LIST, e0, e1);
+ }
+ }
+
+ static final class ListN<E> extends AbstractList<E> implements RandomAccess, Serializable {
+ private final E[] elements;
+
+ @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]);
+ }
+ this.elements = tmp;
+ }
+
+ @Override
+ public int size() {
+ return elements.length;
+ }
+
+ @Override
+ public E get(int index) {
+ Objects.checkIndex(index, elements.length);
+ 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_LIST, elements);
+ }
+ }
+
+ // ---------- Set Implementations ----------
+
+ static final class Set0<E> extends AbstractSet<E> implements Serializable {
+ Set0() { }
+
+ @Override
+ public int size() {
+ return 0;
+ }
+
+ @Override
+ public boolean contains(Object o) {
+ return super.contains(Objects.requireNonNull(o));
+ }
+
+ @Override
+ public Iterator<E> iterator() {
+ return Collections.emptyIterator();
+ }
+
+ private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+ throw new InvalidObjectException("not serial proxy");
+ }
+
+ private Object writeReplace() {
+ return new CollSer(CollSer.IMM_SET);
+ }
+ }
+
+ static final class Set1<E> extends AbstractSet<E> implements Serializable {
+ private final E e0;
+
+ Set1(E e0) {
+ this.e0 = Objects.requireNonNull(e0);
+ }
+
+ @Override
+ public int size() {
+ return 1;
+ }
+
+ @Override
+ public boolean contains(Object o) {
+ return super.contains(Objects.requireNonNull(o));
+ }
+
+ @Override
+ public Iterator<E> iterator() {
+ return Collections.singletonIterator(e0);
+ }
+
+ private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+ throw new InvalidObjectException("not serial proxy");
+ }
+
+ private Object writeReplace() {
+ return new CollSer(CollSer.IMM_SET, e0);
+ }
+ }
+
+ static final class Set2<E> extends AbstractSet<E> implements Serializable {
+ private final E e0;
+ private final E e1;
+
+ Set2(E e0, E e1) {
+ Objects.requireNonNull(e0);
+ Objects.requireNonNull(e1);
+
+ if (e0.equals(e1)) {
+ throw new IllegalArgumentException("duplicate element: " + e0);
+ }
+
+ if (SALT >= 0) {
+ this.e0 = e0;
+ this.e1 = e1;
+ } else {
+ this.e0 = e1;
+ this.e1 = e0;
+ }
+ }
+
+ @Override
+ public int size() {
+ return 2;
+ }
+
+ @Override
+ public boolean contains(Object o) {
+ return super.contains(Objects.requireNonNull(o));
+ }
+
+ @Override
+ public Iterator<E> iterator() {
+ return new Iterator<E>() {
+ private int idx = 0;
+
+ @Override
+ public boolean hasNext() {
+ return idx < 2;
+ }
+
+ @Override
+ public E next() {
+ if (idx == 0) {
+ idx = 1;
+ return e0;
+ } else if (idx == 1) {
+ idx = 2;
+ return e1;
+ } else {
+ throw new NoSuchElementException();
+ }
+ }
+ };
+ }
+
+ private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+ throw new InvalidObjectException("not serial proxy");
+ }
+
+ private Object writeReplace() {
+ 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 AbstractSet<E> implements Serializable {
+ private final E[] elements;
+ private final int size;
+
+ @SafeVarargs
+ @SuppressWarnings("unchecked")
+ SetN(E... input) {
+ size = input.length; // implicit nullcheck of input
+
+ elements = (E[])new Object[(int)Math.ceil(EXPAND_FACTOR * input.length)];
+ for (int i = 0; i < input.length; i++) {
+ E e = Objects.requireNonNull(input[i]);
+ int idx = probe(e);
+ if (idx >= 0) {
+ throw new IllegalArgumentException("duplicate element: " + e);
+ } else {
+ elements[-(idx + 1)] = e;
+ }
+ }
+ }
+
+ @Override
+ public int size() {
+ return size;
+ }
+
+ @Override
+ public boolean contains(Object o) {
+ Objects.requireNonNull(o);
+ return probe(o) >= 0;
+ }
+
+ @Override
+ public Iterator<E> iterator() {
+ return new Iterator<E>() {
+ private int idx = 0;
+
+ @Override
+ public boolean hasNext() {
+ while (idx < elements.length) {
+ if (elements[idx] != null)
+ return true;
+ idx++;
+ }
+ return false;
+ }
+
+ @Override
+ public E next() {
+ if (! hasNext()) {
+ throw new NoSuchElementException();
+ }
+ return elements[idx++];
+ }
+ };
+ }
+
+ // returns index at which element is present; or if absent,
+ // (-i - 1) where i is location where element should be inserted
+ private int probe(Object pe) {
+ int idx = Math.floorMod(pe.hashCode() ^ SALT, elements.length);
+ while (true) {
+ E ee = elements[idx];
+ if (ee == null) {
+ return -idx - 1;
+ } else if (pe.equals(ee)) {
+ return idx;
+ } else if (++idx == elements.length) {
+ idx = 0;
+ }
+ }
+ }
+
+ private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+ throw new InvalidObjectException("not serial proxy");
+ }
+
+ private Object writeReplace() {
+ Object[] array = new Object[size];
+ int dest = 0;
+ for (Object o : elements) {
+ if (o != null) {
+ array[dest++] = o;
+ }
+ }
+ return new CollSer(CollSer.IMM_SET, array);
+ }
+ }
+
+ // ---------- Map Implementations ----------
+
+ static final class Map0<K,V> extends AbstractMap<K,V> implements Serializable {
+ Map0() { }
+
+ @Override
+ public Set<Map.Entry<K,V>> entrySet() {
+ return Set.of();
+ }
+
+ @Override
+ public boolean containsKey(Object o) {
+ return super.containsKey(Objects.requireNonNull(o));
+ }
+
+ @Override
+ public boolean containsValue(Object o) {
+ return super.containsValue(Objects.requireNonNull(o));
+ }
+
+ private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+ throw new InvalidObjectException("not serial proxy");
+ }
+
+ private Object writeReplace() {
+ return new CollSer(CollSer.IMM_MAP);
+ }
+ }
+
+ static final class Map1<K,V> extends AbstractMap<K,V> implements Serializable {
+ private final K k0;
+ private final V v0;
+
+ Map1(K k0, V v0) {
+ this.k0 = Objects.requireNonNull(k0);
+ this.v0 = Objects.requireNonNull(v0);
+ }
+
+ @Override
+ public Set<Map.Entry<K,V>> entrySet() {
+ return Set.of(new KeyValueHolder<>(k0, v0));
+ }
+
+ @Override
+ public boolean containsKey(Object o) {
+ return super.containsKey(Objects.requireNonNull(o));
+ }
+
+ @Override
+ public boolean containsValue(Object o) {
+ return super.containsValue(Objects.requireNonNull(o));
+ }
+
+ private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+ throw new InvalidObjectException("not serial proxy");
+ }
+
+ private Object writeReplace() {
+ return new CollSer(CollSer.IMM_MAP, k0, v0);
+ }
+ }
+
+ /**
+ * An array-based Map implementation. There is a single array "table" that
+ * contains keys and values interleaved: table[0] is kA, table[1] is vA,
+ * table[2] is kB, table[3] is vB, etc. The table size must be even. It must
+ * also be strictly larger than the size (the number of key-value pairs contained
+ * 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 AbstractMap<K,V> implements Serializable {
+ private final Object[] table; // pairs of key, value
+ private final int size; // number of pairs
+
+ MapN(Object... input) {
+ Objects.requireNonNull(input);
+ if ((input.length & 1) != 0) {
+ throw new InternalError("length is odd");
+ }
+ size = input.length >> 1;
+
+ int len = (int)Math.ceil(EXPAND_FACTOR * input.length);
+ len = (len + 1) & ~1; // ensure table is even length
+ table = new Object[len];
+
+ for (int i = 0; i < input.length; i += 2) {
+ @SuppressWarnings("unchecked")
+ K k = Objects.requireNonNull((K)input[i]);
+ @SuppressWarnings("unchecked")
+ V v = Objects.requireNonNull((V)input[i+1]);
+ int idx = probe(k);
+ if (idx >= 0) {
+ throw new IllegalArgumentException("duplicate key: " + k);
+ } else {
+ int dest = -(idx + 1);
+ table[dest] = k;
+ table[dest+1] = v;
+ }
+ }
+ }
+
+ @Override
+ public boolean containsKey(Object o) {
+ return probe(Objects.requireNonNull(o)) >= 0;
+ }
+
+ @Override
+ public boolean containsValue(Object o) {
+ return super.containsValue(Objects.requireNonNull(o));
+ }
+
+ @Override
+ @SuppressWarnings("unchecked")
+ public V get(Object o) {
+ int i = probe(o);
+ if (i >= 0) {
+ return (V)table[i+1];
+ } else {
+ return null;
+ }
+ }
+
+ @Override
+ public int size() {
+ return size;
+ }
+
+ @Override
+ public Set<Map.Entry<K,V>> entrySet() {
+ return new AbstractSet<Map.Entry<K,V>>() {
+ @Override
+ public int size() {
+ return MapN.this.size;
+ }
+
+ @Override
+ public Iterator<Map.Entry<K,V>> iterator() {
+ return new Iterator<Map.Entry<K,V>>() {
+ int idx = 0;
+
+ @Override
+ public boolean hasNext() {
+ while (idx < table.length) {
+ if (table[idx] != null)
+ return true;
+ idx += 2;
+ }
+ return false;
+ }
+
+ @Override
+ public Map.Entry<K,V> next() {
+ if (hasNext()) {
+ @SuppressWarnings("unchecked")
+ Map.Entry<K,V> e =
+ new KeyValueHolder<>((K)table[idx], (V)table[idx+1]);
+ idx += 2;
+ return e;
+ } else {
+ throw new NoSuchElementException();
+ }
+ }
+ };
+ }
+ };
+ }
+
+ // returns index at which the probe key is present; or if absent,
+ // (-i - 1) where i is location where element should be inserted
+ private int probe(Object pk) {
+ int idx = Math.floorMod(pk.hashCode() ^ SALT, table.length >> 1) << 1;
+ while (true) {
+ @SuppressWarnings("unchecked")
+ K ek = (K)table[idx];
+ if (ek == null) {
+ return -idx - 1;
+ } else if (pk.equals(ek)) {
+ return idx;
+ } else if ((idx += 2) == table.length) {
+ idx = 0;
+ }
+ }
+ }
+
+ private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+ throw new InvalidObjectException("not serial proxy");
+ }
+
+ private Object writeReplace() {
+ Object[] array = new Object[2 * size];
+ int len = table.length;
+ int dest = 0;
+ for (int i = 0; i < len; i += 2) {
+ if (table[i] != null) {
+ array[dest++] = table[i];
+ array[dest++] = table[i+1];
+ }
+ }
+ return new CollSer(CollSer.IMM_MAP, array);
+ }
+ }
+}
+
+// ---------- Serialization Proxy ----------
+
+/**
+ * Serialization proxy class for immutable collections.
+ */
+final class CollSer implements Serializable {
+ private static final long serialVersionUID = 6309168927139932177L;
+
+ static final int IMM_LIST = 1;
+ static final int IMM_SET = 2;
+ static final int IMM_MAP = 3;
+
+ private final int flags;
+ private final Object[] array;
+
+ CollSer(int f, Object... a) {
+ flags = f;
+ array = a;
+ }
+
+ private Object readResolve() throws ObjectStreamException {
+ try {
+ if (array == null) {
+ throw new InvalidObjectException("null array");
+ }
+
+ // use low order 8 bits to indicate "kind"
+ // ignore high order bits
+ switch (flags & 0xff) {
+ case IMM_LIST:
+ return List.of(array);
+ case IMM_SET:
+ return Set.of(array);
+ case IMM_MAP:
+ if (array.length == 0) {
+ return new ImmutableCollections.Map0<>();
+ } else if (array.length == 2) {
+ return new ImmutableCollections.Map1<>(array[0], array[1]);
+ } else {
+ return new ImmutableCollections.MapN<>(array);
+ }
+ default:
+ throw new InvalidObjectException(String.format("invalid flags 0x%x", flags));
+ }
+ } catch (NullPointerException|IllegalArgumentException ex) {
+ InvalidObjectException ioe = new InvalidObjectException("invalid object");
+ ioe.initCause(ex);
+ throw ioe;
+ }
+ }
+}
--- a/jdk/src/java.base/share/classes/java/util/List.java Fri May 06 12:48:19 2016 +0000
+++ b/jdk/src/java.base/share/classes/java/util/List.java Fri May 06 11:33:32 2016 -0700
@@ -765,7 +765,7 @@
* @since 9
*/
static <E> List<E> of() {
- return Collections.emptyList();
+ return new ImmutableCollections.List0<>();
}
/**
@@ -781,7 +781,7 @@
* @since 9
*/
static <E> List<E> of(E e1) {
- return Collections.singletonList(Objects.requireNonNull(e1));
+ return new ImmutableCollections.List1<>(e1);
}
/**
@@ -798,9 +798,7 @@
* @since 9
*/
static <E> List<E> of(E e1, E e2) {
- return Collections.unmodifiableList(
- Arrays.asList(Objects.requireNonNull(e1),
- Objects.requireNonNull(e2)));
+ return new ImmutableCollections.List2<>(e1, e2);
}
/**
@@ -818,10 +816,7 @@
* @since 9
*/
static <E> List<E> of(E e1, E e2, E e3) {
- return Collections.unmodifiableList(
- Arrays.asList(Objects.requireNonNull(e1),
- Objects.requireNonNull(e2),
- Objects.requireNonNull(e3)));
+ return new ImmutableCollections.ListN<>(e1, e2, e3);
}
/**
@@ -840,11 +835,7 @@
* @since 9
*/
static <E> List<E> of(E e1, E e2, E e3, E e4) {
- return Collections.unmodifiableList(
- Arrays.asList(Objects.requireNonNull(e1),
- Objects.requireNonNull(e2),
- Objects.requireNonNull(e3),
- Objects.requireNonNull(e4)));
+ return new ImmutableCollections.ListN<>(e1, e2, e3, e4);
}
/**
@@ -864,12 +855,7 @@
* @since 9
*/
static <E> List<E> of(E e1, E e2, E e3, E e4, E e5) {
- return Collections.unmodifiableList(
- Arrays.asList(Objects.requireNonNull(e1),
- Objects.requireNonNull(e2),
- Objects.requireNonNull(e3),
- Objects.requireNonNull(e4),
- Objects.requireNonNull(e5)));
+ return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5);
}
/**
@@ -890,13 +876,8 @@
* @since 9
*/
static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6) {
- return Collections.unmodifiableList(
- Arrays.asList(Objects.requireNonNull(e1),
- Objects.requireNonNull(e2),
- Objects.requireNonNull(e3),
- Objects.requireNonNull(e4),
- Objects.requireNonNull(e5),
- Objects.requireNonNull(e6)));
+ return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5,
+ e6);
}
/**
@@ -918,14 +899,8 @@
* @since 9
*/
static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7) {
- return Collections.unmodifiableList(
- Arrays.asList(Objects.requireNonNull(e1),
- Objects.requireNonNull(e2),
- Objects.requireNonNull(e3),
- Objects.requireNonNull(e4),
- Objects.requireNonNull(e5),
- Objects.requireNonNull(e6),
- Objects.requireNonNull(e7)));
+ return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5,
+ e6, e7);
}
/**
@@ -948,15 +923,8 @@
* @since 9
*/
static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8) {
- return Collections.unmodifiableList(
- Arrays.asList(Objects.requireNonNull(e1),
- Objects.requireNonNull(e2),
- Objects.requireNonNull(e3),
- Objects.requireNonNull(e4),
- Objects.requireNonNull(e5),
- Objects.requireNonNull(e6),
- Objects.requireNonNull(e7),
- Objects.requireNonNull(e8)));
+ return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5,
+ e6, e7, e8);
}
/**
@@ -980,16 +948,8 @@
* @since 9
*/
static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9) {
- return Collections.unmodifiableList(
- Arrays.asList(Objects.requireNonNull(e1),
- Objects.requireNonNull(e2),
- Objects.requireNonNull(e3),
- Objects.requireNonNull(e4),
- Objects.requireNonNull(e5),
- Objects.requireNonNull(e6),
- Objects.requireNonNull(e7),
- Objects.requireNonNull(e8),
- Objects.requireNonNull(e9)));
+ return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5,
+ e6, e7, e8, e9);
}
/**
@@ -1014,17 +974,8 @@
* @since 9
*/
static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10) {
- return Collections.unmodifiableList(
- Arrays.asList(Objects.requireNonNull(e1),
- Objects.requireNonNull(e2),
- Objects.requireNonNull(e3),
- Objects.requireNonNull(e4),
- Objects.requireNonNull(e5),
- Objects.requireNonNull(e6),
- Objects.requireNonNull(e7),
- Objects.requireNonNull(e8),
- Objects.requireNonNull(e9),
- Objects.requireNonNull(e10)));
+ return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5,
+ e6, e7, e8, e9, e10);
}
/**
@@ -1055,10 +1006,16 @@
@SafeVarargs
@SuppressWarnings("varargs")
static <E> List<E> of(E... elements) {
- elements = elements.clone(); // throws NPE if es is null
- for (E e : elements) {
- Objects.requireNonNull(e);
+ Objects.requireNonNull(elements);
+ switch (elements.length) {
+ case 0:
+ return new ImmutableCollections.List0<>();
+ case 1:
+ return new ImmutableCollections.List1<>(elements[0]);
+ case 2:
+ return new ImmutableCollections.List2<>(elements[0], elements[1]);
+ default:
+ return new ImmutableCollections.ListN<>(elements);
}
- return Collections.unmodifiableList(Arrays.asList(elements));
}
}
--- a/jdk/src/java.base/share/classes/java/util/Map.java Fri May 06 12:48:19 2016 +0000
+++ b/jdk/src/java.base/share/classes/java/util/Map.java Fri May 06 11:33:32 2016 -0700
@@ -1282,7 +1282,7 @@
* @since 9
*/
static <K, V> Map<K, V> of() {
- return Collections.emptyMap();
+ return new ImmutableCollections.Map0<>();
}
/**
@@ -1299,7 +1299,7 @@
* @since 9
*/
static <K, V> Map<K, V> of(K k1, V v1) {
- return Collections.singletonMap(Objects.requireNonNull(k1), Objects.requireNonNull(v1));
+ return new ImmutableCollections.Map1<>(k1, v1);
}
/**
@@ -1319,13 +1319,7 @@
* @since 9
*/
static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2) {
- Map<K, V> map = new HashMap<>(3); // specify number of buckets to avoid resizing
- map.put(Objects.requireNonNull(k1), Objects.requireNonNull(v1));
- map.put(Objects.requireNonNull(k2), Objects.requireNonNull(v2));
- if (map.size() != 2) {
- throw new IllegalArgumentException("duplicate keys");
- }
- return Collections.unmodifiableMap(map);
+ return new ImmutableCollections.MapN<>(k1, v1, k2, v2);
}
/**
@@ -1347,14 +1341,7 @@
* @since 9
*/
static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3) {
- Map<K, V> map = new HashMap<>(5); // specify number of buckets to avoid resizing
- map.put(Objects.requireNonNull(k1), Objects.requireNonNull(v1));
- map.put(Objects.requireNonNull(k2), Objects.requireNonNull(v2));
- map.put(Objects.requireNonNull(k3), Objects.requireNonNull(v3));
- if (map.size() != 3) {
- throw new IllegalArgumentException("duplicate keys");
- }
- return Collections.unmodifiableMap(map);
+ return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3);
}
/**
@@ -1378,15 +1365,7 @@
* @since 9
*/
static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
- Map<K, V> map = new HashMap<>(6); // specify number of buckets to avoid resizing
- map.put(Objects.requireNonNull(k1), Objects.requireNonNull(v1));
- map.put(Objects.requireNonNull(k2), Objects.requireNonNull(v2));
- map.put(Objects.requireNonNull(k3), Objects.requireNonNull(v3));
- map.put(Objects.requireNonNull(k4), Objects.requireNonNull(v4));
- if (map.size() != 4) {
- throw new IllegalArgumentException("duplicate keys");
- }
- return Collections.unmodifiableMap(map);
+ return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4);
}
/**
@@ -1412,16 +1391,7 @@
* @since 9
*/
static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
- Map<K, V> map = new HashMap<>(7); // specify number of buckets to avoid resizing
- map.put(Objects.requireNonNull(k1), Objects.requireNonNull(v1));
- map.put(Objects.requireNonNull(k2), Objects.requireNonNull(v2));
- map.put(Objects.requireNonNull(k3), Objects.requireNonNull(v3));
- map.put(Objects.requireNonNull(k4), Objects.requireNonNull(v4));
- map.put(Objects.requireNonNull(k5), Objects.requireNonNull(v5));
- if (map.size() != 5) {
- throw new IllegalArgumentException("duplicate keys");
- }
- return Collections.unmodifiableMap(map);
+ return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5);
}
/**
@@ -1450,17 +1420,8 @@
*/
static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5,
K k6, V v6) {
- Map<K, V> map = new HashMap<>(9); // specify number of buckets to avoid resizing
- map.put(Objects.requireNonNull(k1), Objects.requireNonNull(v1));
- map.put(Objects.requireNonNull(k2), Objects.requireNonNull(v2));
- map.put(Objects.requireNonNull(k3), Objects.requireNonNull(v3));
- map.put(Objects.requireNonNull(k4), Objects.requireNonNull(v4));
- map.put(Objects.requireNonNull(k5), Objects.requireNonNull(v5));
- map.put(Objects.requireNonNull(k6), Objects.requireNonNull(v6));
- if (map.size() != 6) {
- throw new IllegalArgumentException("duplicate keys");
- }
- return Collections.unmodifiableMap(map);
+ return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5,
+ k6, v6);
}
/**
@@ -1491,18 +1452,8 @@
*/
static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5,
K k6, V v6, K k7, V v7) {
- Map<K, V> map = new HashMap<>(10); // specify number of buckets to avoid resizing
- map.put(Objects.requireNonNull(k1), Objects.requireNonNull(v1));
- map.put(Objects.requireNonNull(k2), Objects.requireNonNull(v2));
- map.put(Objects.requireNonNull(k3), Objects.requireNonNull(v3));
- map.put(Objects.requireNonNull(k4), Objects.requireNonNull(v4));
- map.put(Objects.requireNonNull(k5), Objects.requireNonNull(v5));
- map.put(Objects.requireNonNull(k6), Objects.requireNonNull(v6));
- map.put(Objects.requireNonNull(k7), Objects.requireNonNull(v7));
- if (map.size() != 7) {
- throw new IllegalArgumentException("duplicate keys");
- }
- return Collections.unmodifiableMap(map);
+ return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5,
+ k6, v6, k7, v7);
}
/**
@@ -1535,19 +1486,8 @@
*/
static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5,
K k6, V v6, K k7, V v7, K k8, V v8) {
- Map<K, V> map = new HashMap<>(11); // specify number of buckets to avoid resizing
- map.put(Objects.requireNonNull(k1), Objects.requireNonNull(v1));
- map.put(Objects.requireNonNull(k2), Objects.requireNonNull(v2));
- map.put(Objects.requireNonNull(k3), Objects.requireNonNull(v3));
- map.put(Objects.requireNonNull(k4), Objects.requireNonNull(v4));
- map.put(Objects.requireNonNull(k5), Objects.requireNonNull(v5));
- map.put(Objects.requireNonNull(k6), Objects.requireNonNull(v6));
- map.put(Objects.requireNonNull(k7), Objects.requireNonNull(v7));
- map.put(Objects.requireNonNull(k8), Objects.requireNonNull(v8));
- if (map.size() != 8) {
- throw new IllegalArgumentException("duplicate keys");
- }
- return Collections.unmodifiableMap(map);
+ return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5,
+ k6, v6, k7, v7, k8, v8);
}
/**
@@ -1582,20 +1522,8 @@
*/
static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5,
K k6, V v6, K k7, V v7, K k8, V v8, K k9, V v9) {
- Map<K, V> map = new HashMap<>(13); // specify number of buckets to avoid resizing
- map.put(Objects.requireNonNull(k1), Objects.requireNonNull(v1));
- map.put(Objects.requireNonNull(k2), Objects.requireNonNull(v2));
- map.put(Objects.requireNonNull(k3), Objects.requireNonNull(v3));
- map.put(Objects.requireNonNull(k4), Objects.requireNonNull(v4));
- map.put(Objects.requireNonNull(k5), Objects.requireNonNull(v5));
- map.put(Objects.requireNonNull(k6), Objects.requireNonNull(v6));
- map.put(Objects.requireNonNull(k7), Objects.requireNonNull(v7));
- map.put(Objects.requireNonNull(k8), Objects.requireNonNull(v8));
- map.put(Objects.requireNonNull(k9), Objects.requireNonNull(v9));
- if (map.size() != 9) {
- throw new IllegalArgumentException("duplicate keys");
- }
- return Collections.unmodifiableMap(map);
+ return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5,
+ k6, v6, k7, v7, k8, v8, k9, v9);
}
/**
@@ -1632,21 +1560,8 @@
*/
static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5,
K k6, V v6, K k7, V v7, K k8, V v8, K k9, V v9, K k10, V v10) {
- Map<K, V> map = new HashMap<>(14); // specify number of buckets to avoid resizing
- map.put(Objects.requireNonNull(k1), Objects.requireNonNull(v1));
- map.put(Objects.requireNonNull(k2), Objects.requireNonNull(v2));
- map.put(Objects.requireNonNull(k3), Objects.requireNonNull(v3));
- map.put(Objects.requireNonNull(k4), Objects.requireNonNull(v4));
- map.put(Objects.requireNonNull(k5), Objects.requireNonNull(v5));
- map.put(Objects.requireNonNull(k6), Objects.requireNonNull(v6));
- map.put(Objects.requireNonNull(k7), Objects.requireNonNull(v7));
- map.put(Objects.requireNonNull(k8), Objects.requireNonNull(v8));
- map.put(Objects.requireNonNull(k9), Objects.requireNonNull(v9));
- map.put(Objects.requireNonNull(k10), Objects.requireNonNull(v10));
- if (map.size() != 10) {
- throw new IllegalArgumentException("duplicate keys");
- }
- return Collections.unmodifiableMap(map);
+ return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5,
+ k6, v6, k7, v7, k8, v8, k9, v9, k10, v10);
}
/**
@@ -1683,15 +1598,21 @@
@SafeVarargs
@SuppressWarnings("varargs")
static <K, V> Map<K, V> ofEntries(Entry<? extends K, ? extends V>... entries) {
- Map<K, V> map = new HashMap<>(entries.length * 4 / 3 + 1); // throws NPE if entries is null
- for (Entry<? extends K, ? extends V> e : entries) {
- // next line throws NPE if e is null
- map.put(Objects.requireNonNull(e.getKey()), Objects.requireNonNull(e.getValue()));
+ Objects.requireNonNull(entries);
+ if (entries.length == 0) {
+ return new ImmutableCollections.Map0<>();
+ } else if (entries.length == 1) {
+ return new ImmutableCollections.Map1<>(entries[0].getKey(),
+ entries[0].getValue());
+ } else {
+ Object[] kva = new Object[entries.length << 1];
+ int a = 0;
+ for (Entry<? extends K, ? extends V> entry : entries) {
+ kva[a++] = entry.getKey();
+ kva[a++] = entry.getValue();
+ }
+ return new ImmutableCollections.MapN<>(kva);
}
- if (map.size() != entries.length) {
- throw new IllegalArgumentException("duplicate keys");
- }
- return Collections.unmodifiableMap(map);
}
/**
--- a/jdk/src/java.base/share/classes/java/util/Set.java Fri May 06 12:48:19 2016 +0000
+++ b/jdk/src/java.base/share/classes/java/util/Set.java Fri May 06 11:33:32 2016 -0700
@@ -444,7 +444,7 @@
* @since 9
*/
static <E> Set<E> of() {
- return Collections.emptySet();
+ return new ImmutableCollections.Set0<>();
}
/**
@@ -459,7 +459,7 @@
* @since 9
*/
static <E> Set<E> of(E e1) {
- return Collections.singleton(Objects.requireNonNull(e1));
+ return new ImmutableCollections.Set1<>(e1);
}
/**
@@ -476,12 +476,7 @@
* @since 9
*/
static <E> Set<E> of(E e1, E e2) {
- Set<E> set = new HashSet<>(Arrays.asList(Objects.requireNonNull(e1),
- Objects.requireNonNull(e2)));
- if (set.size() != 2) {
- throw new IllegalArgumentException("duplicate elements");
- }
- return Collections.unmodifiableSet(set);
+ return new ImmutableCollections.Set2<>(e1, e2);
}
/**
@@ -499,13 +494,7 @@
* @since 9
*/
static <E> Set<E> of(E e1, E e2, E e3) {
- Set<E> set = new HashSet<>(Arrays.asList(Objects.requireNonNull(e1),
- Objects.requireNonNull(e2),
- Objects.requireNonNull(e3)));
- if (set.size() != 3) {
- throw new IllegalArgumentException("duplicate elements");
- }
- return Collections.unmodifiableSet(set);
+ return new ImmutableCollections.SetN<>(e1, e2, e3);
}
/**
@@ -524,14 +513,7 @@
* @since 9
*/
static <E> Set<E> of(E e1, E e2, E e3, E e4) {
- Set<E> set = new HashSet<>(Arrays.asList(Objects.requireNonNull(e1),
- Objects.requireNonNull(e2),
- Objects.requireNonNull(e3),
- Objects.requireNonNull(e4)));
- if (set.size() != 4) {
- throw new IllegalArgumentException("duplicate elements");
- }
- return Collections.unmodifiableSet(set);
+ return new ImmutableCollections.SetN<>(e1, e2, e3, e4);
}
/**
@@ -551,15 +533,7 @@
* @since 9
*/
static <E> Set<E> of(E e1, E e2, E e3, E e4, E e5) {
- Set<E> set = new HashSet<>(Arrays.asList(Objects.requireNonNull(e1),
- Objects.requireNonNull(e2),
- Objects.requireNonNull(e3),
- Objects.requireNonNull(e4),
- Objects.requireNonNull(e5)));
- if (set.size() != 5) {
- throw new IllegalArgumentException("duplicate elements");
- }
- return Collections.unmodifiableSet(set);
+ return new ImmutableCollections.SetN<>(e1, e2, e3, e4, e5);
}
/**
@@ -580,16 +554,8 @@
* @since 9
*/
static <E> Set<E> of(E e1, E e2, E e3, E e4, E e5, E e6) {
- Set<E> set = new HashSet<>(Arrays.asList(Objects.requireNonNull(e1),
- Objects.requireNonNull(e2),
- Objects.requireNonNull(e3),
- Objects.requireNonNull(e4),
- Objects.requireNonNull(e5),
- Objects.requireNonNull(e6)));
- if (set.size() != 6) {
- throw new IllegalArgumentException("duplicate elements");
- }
- return Collections.unmodifiableSet(set);
+ return new ImmutableCollections.SetN<>(e1, e2, e3, e4, e5,
+ e6);
}
/**
@@ -611,17 +577,8 @@
* @since 9
*/
static <E> Set<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7) {
- Set<E> set = new HashSet<>(Arrays.asList(Objects.requireNonNull(e1),
- Objects.requireNonNull(e2),
- Objects.requireNonNull(e3),
- Objects.requireNonNull(e4),
- Objects.requireNonNull(e5),
- Objects.requireNonNull(e6),
- Objects.requireNonNull(e7)));
- if (set.size() != 7) {
- throw new IllegalArgumentException("duplicate elements");
- }
- return Collections.unmodifiableSet(set);
+ return new ImmutableCollections.SetN<>(e1, e2, e3, e4, e5,
+ e6, e7);
}
/**
@@ -644,18 +601,8 @@
* @since 9
*/
static <E> Set<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8) {
- Set<E> set = new HashSet<>(Arrays.asList(Objects.requireNonNull(e1),
- Objects.requireNonNull(e2),
- Objects.requireNonNull(e3),
- Objects.requireNonNull(e4),
- Objects.requireNonNull(e5),
- Objects.requireNonNull(e6),
- Objects.requireNonNull(e7),
- Objects.requireNonNull(e8)));
- if (set.size() != 8) {
- throw new IllegalArgumentException("duplicate elements");
- }
- return Collections.unmodifiableSet(set);
+ return new ImmutableCollections.SetN<>(e1, e2, e3, e4, e5,
+ e6, e7, e8);
}
/**
@@ -679,19 +626,8 @@
* @since 9
*/
static <E> Set<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9) {
- Set<E> set = new HashSet<>(Arrays.asList(Objects.requireNonNull(e1),
- Objects.requireNonNull(e2),
- Objects.requireNonNull(e3),
- Objects.requireNonNull(e4),
- Objects.requireNonNull(e5),
- Objects.requireNonNull(e6),
- Objects.requireNonNull(e7),
- Objects.requireNonNull(e8),
- Objects.requireNonNull(e9)));
- if (set.size() != 9) {
- throw new IllegalArgumentException("duplicate elements");
- }
- return Collections.unmodifiableSet(set);
+ return new ImmutableCollections.SetN<>(e1, e2, e3, e4, e5,
+ e6, e7, e8, e9);
}
/**
@@ -716,20 +652,8 @@
* @since 9
*/
static <E> Set<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10) {
- Set<E> set = new HashSet<>(Arrays.asList(Objects.requireNonNull(e1),
- Objects.requireNonNull(e2),
- Objects.requireNonNull(e3),
- Objects.requireNonNull(e4),
- Objects.requireNonNull(e5),
- Objects.requireNonNull(e6),
- Objects.requireNonNull(e7),
- Objects.requireNonNull(e8),
- Objects.requireNonNull(e9),
- Objects.requireNonNull(e10)));
- if (set.size() != 10) {
- throw new IllegalArgumentException("duplicate elements");
- }
- return Collections.unmodifiableSet(set);
+ return new ImmutableCollections.SetN<>(e1, e2, e3, e4, e5,
+ e6, e7, e8, e9, e10);
}
/**
@@ -759,15 +683,18 @@
* @since 9
*/
@SafeVarargs
+ @SuppressWarnings("varargs")
static <E> Set<E> of(E... elements) {
- for (E e : elements) { // throws NPE if es is null
- Objects.requireNonNull(e);
+ Objects.requireNonNull(elements);
+ switch (elements.length) {
+ case 0:
+ return new ImmutableCollections.Set0<>();
+ case 1:
+ return new ImmutableCollections.Set1<>(elements[0]);
+ case 2:
+ return new ImmutableCollections.Set2<>(elements[0], elements[1]);
+ default:
+ return new ImmutableCollections.SetN<>(elements);
}
- @SuppressWarnings("varargs")
- Set<E> set = new HashSet<>(Arrays.asList(elements));
- if (set.size() != elements.length) {
- throw new IllegalArgumentException("duplicate elements");
- }
- return Collections.unmodifiableSet(set);
}
}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/Map/EntrySetIterator.java Fri May 06 11:33:32 2016 -0700
@@ -0,0 +1,52 @@
+/*
+ * Copyright (c) 2016, 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
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * @test
+ * @bug 8139233
+ * @summary ensure entry set's iterator doesn't have side effects on the entry set
+ * @run testng EntrySetIterator
+ */
+
+import java.util.*;
+import org.testng.annotations.Test;
+import static org.testng.Assert.assertTrue;
+import static org.testng.Assert.assertEquals;
+
+public class EntrySetIterator {
+ @Test
+ public void main() {
+ Map<String, String> map = Map.of("a", "1", "b", "2", "c", "3");
+ Set<Map.Entry<String, String>> entrySet = map.entrySet();
+ Iterator<Map.Entry<String, String>> iterator = entrySet.iterator();
+
+ assertTrue(iterator.hasNext());
+
+ // copying implicitly iterates an iterator
+ Set<Map.Entry<String, String>> copy1 = new HashSet<>(entrySet);
+ Set<Map.Entry<String, String>> copy2 = new HashSet<>(entrySet);
+
+ assertEquals(copy2, copy1);
+ assertTrue(iterator.hasNext());
+ }
+}