--- a/jdk/src/share/classes/java/util/IdentityHashMap.java Wed Apr 17 14:39:04 2013 -0400
+++ b/jdk/src/share/classes/java/util/IdentityHashMap.java Wed Apr 17 11:34:31 2013 +0200
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2000, 2012, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2000, 2013, 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
@@ -24,8 +24,10 @@
*/
package java.util;
+
import java.io.*;
import java.lang.reflect.Array;
+import java.util.function.Consumer;
/**
* This class implements the <tt>Map</tt> interface with a hash table, using
@@ -162,19 +164,19 @@
/**
* The table, resized as necessary. Length MUST always be a power of two.
*/
- private transient Object[] table;
+ transient Object[] table; // non-private to simplify nested class access
/**
* The number of key-value mappings contained in this identity hash map.
*
* @serial
*/
- private int size;
+ int size;
/**
* The number of modifications, to support fast-fail iterators
*/
- private transient int modCount;
+ transient int modCount;
/**
* The next size value at which to resize (capacity * load factor).
@@ -184,7 +186,7 @@
/**
* Value representing null keys inside tables.
*/
- private static final Object NULL_KEY = new Object();
+ static final Object NULL_KEY = new Object();
/**
* Use NULL_KEY for key if it is null.
@@ -196,7 +198,7 @@
/**
* Returns internal representation of null key back to caller as null.
*/
- private static Object unmaskNull(Object key) {
+ static final Object unmaskNull(Object key) {
return (key == NULL_KEY ? null : key);
}
@@ -1012,7 +1014,7 @@
return result;
}
public Object[] toArray() {
- return toArray(new Object[size()]);
+ return toArray(new Object[0]);
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
@@ -1042,6 +1044,10 @@
}
return a;
}
+
+ public Spliterator<K> spliterator() {
+ return new KeySpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
+ }
}
/**
@@ -1095,7 +1101,7 @@
IdentityHashMap.this.clear();
}
public Object[] toArray() {
- return toArray(new Object[size()]);
+ return toArray(new Object[0]);
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
@@ -1124,6 +1130,10 @@
}
return a;
}
+
+ public Spliterator<V> spliterator() {
+ return new ValueSpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
+ }
}
/**
@@ -1211,7 +1221,7 @@
}
public Object[] toArray() {
- return toArray(new Object[size()]);
+ return toArray(new Object[0]);
}
@SuppressWarnings("unchecked")
@@ -1242,6 +1252,10 @@
}
return a;
}
+
+ public Spliterator<Map.Entry<K,V>> spliterator() {
+ return new EntrySpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
+ }
}
@@ -1322,4 +1336,223 @@
tab[i] = k;
tab[i + 1] = value;
}
+
+ /**
+ * Similar form as array-based Spliterators, but skips blank elements,
+ * and guestimates size as decreasing by half per split.
+ */
+ static class IdentityHashMapSpliterator<K,V> {
+ final IdentityHashMap<K,V> map;
+ int index; // current index, modified on advance/split
+ int fence; // -1 until first use; then one past last index
+ int est; // size estimate
+ int expectedModCount; // initialized when fence set
+
+ IdentityHashMapSpliterator(IdentityHashMap<K,V> map, int origin,
+ int fence, int est, int expectedModCount) {
+ this.map = map;
+ this.index = origin;
+ this.fence = fence;
+ this.est = est;
+ this.expectedModCount = expectedModCount;
+ }
+
+ final int getFence() { // initialize fence and size on first use
+ int hi;
+ if ((hi = fence) < 0) {
+ est = map.size;
+ expectedModCount = map.modCount;
+ hi = fence = map.table.length;
+ }
+ return hi;
+ }
+
+ public final long estimateSize() {
+ getFence(); // force init
+ return (long) est;
+ }
+ }
+
+ static final class KeySpliterator<K,V>
+ extends IdentityHashMapSpliterator<K,V>
+ implements Spliterator<K> {
+ KeySpliterator(IdentityHashMap<K,V> map, int origin, int fence, int est,
+ int expectedModCount) {
+ super(map, origin, fence, est, expectedModCount);
+ }
+
+ public KeySpliterator<K,V> trySplit() {
+ int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
+ return (lo >= mid) ? null :
+ new KeySpliterator<K,V>(map, lo, index = mid, est >>>= 1,
+ expectedModCount);
+ }
+
+ @SuppressWarnings("unchecked")
+ public void forEachRemaining(Consumer<? super K> action) {
+ if (action == null)
+ throw new NullPointerException();
+ int i, hi, mc; Object key;
+ IdentityHashMap<K,V> m; Object[] a;
+ if ((m = map) != null && (a = m.table) != null &&
+ (i = index) >= 0 && (index = hi = getFence()) <= a.length) {
+ for (; i < hi; i += 2) {
+ if ((key = a[i]) != null)
+ action.accept((K)unmaskNull(key));
+ }
+ if (m.modCount == expectedModCount)
+ return;
+ }
+ throw new ConcurrentModificationException();
+ }
+
+ @SuppressWarnings("unchecked")
+ public boolean tryAdvance(Consumer<? super K> action) {
+ if (action == null)
+ throw new NullPointerException();
+ Object[] a = map.table;
+ int hi = getFence();
+ while (index < hi) {
+ Object key = a[index];
+ index += 2;
+ if (key != null) {
+ action.accept((K)unmaskNull(key));
+ if (map.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return true;
+ }
+ }
+ return false;
+ }
+
+ public int characteristics() {
+ return (fence < 0 || est == map.size ? SIZED : 0) | Spliterator.DISTINCT;
+ }
+ }
+
+ static final class ValueSpliterator<K,V>
+ extends IdentityHashMapSpliterator<K,V>
+ implements Spliterator<V> {
+ ValueSpliterator(IdentityHashMap<K,V> m, int origin, int fence, int est,
+ int expectedModCount) {
+ super(m, origin, fence, est, expectedModCount);
+ }
+
+ public ValueSpliterator<K,V> trySplit() {
+ int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
+ return (lo >= mid) ? null :
+ new ValueSpliterator<K,V>(map, lo, index = mid, est >>>= 1,
+ expectedModCount);
+ }
+
+ public void forEachRemaining(Consumer<? super V> action) {
+ if (action == null)
+ throw new NullPointerException();
+ int i, hi, mc;
+ IdentityHashMap<K,V> m; Object[] a;
+ if ((m = map) != null && (a = m.table) != null &&
+ (i = index) >= 0 && (index = hi = getFence()) <= a.length) {
+ for (; i < hi; i += 2) {
+ if (a[i] != null) {
+ @SuppressWarnings("unchecked") V v = (V)a[i+1];
+ action.accept(v);
+ }
+ }
+ if (m.modCount == expectedModCount)
+ return;
+ }
+ throw new ConcurrentModificationException();
+ }
+
+ public boolean tryAdvance(Consumer<? super V> action) {
+ if (action == null)
+ throw new NullPointerException();
+ Object[] a = map.table;
+ int hi = getFence();
+ while (index < hi) {
+ Object key = a[index];
+ @SuppressWarnings("unchecked") V v = (V)a[index+1];
+ index += 2;
+ if (key != null) {
+ action.accept(v);
+ if (map.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return true;
+ }
+ }
+ return false;
+ }
+
+ public int characteristics() {
+ return (fence < 0 || est == map.size ? SIZED : 0);
+ }
+
+ }
+
+ static final class EntrySpliterator<K,V>
+ extends IdentityHashMapSpliterator<K,V>
+ implements Spliterator<Map.Entry<K,V>> {
+ EntrySpliterator(IdentityHashMap<K,V> m, int origin, int fence, int est,
+ int expectedModCount) {
+ super(m, origin, fence, est, expectedModCount);
+ }
+
+ public EntrySpliterator<K,V> trySplit() {
+ int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
+ return (lo >= mid) ? null :
+ new EntrySpliterator<K,V>(map, lo, index = mid, est >>>= 1,
+ expectedModCount);
+ }
+
+ public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) {
+ if (action == null)
+ throw new NullPointerException();
+ int i, hi, mc;
+ IdentityHashMap<K,V> m; Object[] a;
+ if ((m = map) != null && (a = m.table) != null &&
+ (i = index) >= 0 && (index = hi = getFence()) <= a.length) {
+ for (; i < hi; i += 2) {
+ Object key = a[i];
+ if (key != null) {
+ @SuppressWarnings("unchecked") K k =
+ (K)unmaskNull(key);
+ @SuppressWarnings("unchecked") V v = (V)a[i+1];
+ action.accept
+ (new AbstractMap.SimpleImmutableEntry<K,V>(k, v));
+
+ }
+ }
+ if (m.modCount == expectedModCount)
+ return;
+ }
+ throw new ConcurrentModificationException();
+ }
+
+ public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
+ if (action == null)
+ throw new NullPointerException();
+ Object[] a = map.table;
+ int hi = getFence();
+ while (index < hi) {
+ Object key = a[index];
+ @SuppressWarnings("unchecked") V v = (V)a[index+1];
+ index += 2;
+ if (key != null) {
+ @SuppressWarnings("unchecked") K k =
+ (K)unmaskNull(key);
+ action.accept
+ (new AbstractMap.SimpleImmutableEntry<K,V>(k, v));
+ if (map.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return true;
+ }
+ }
+ return false;
+ }
+
+ public int characteristics() {
+ return (fence < 0 || est == map.size ? SIZED : 0) | Spliterator.DISTINCT;
+ }
+ }
+
}