8008167: IdentityHashMap.[keySet|values|entrySet].toArray speed-up
authormduigou
Wed, 13 Feb 2013 14:50:14 -0800
changeset 15997 39590b63ec4c
parent 15996 97dd2e8c7e5e
child 15998 07d54dcb3a56
8008167: IdentityHashMap.[keySet|values|entrySet].toArray speed-up Reviewed-by: mduigou, martin Contributed-by: Peter Levart <peter.levary@gmail.com>
jdk/src/share/classes/java/util/IdentityHashMap.java
--- a/jdk/src/share/classes/java/util/IdentityHashMap.java	Thu Feb 14 13:01:03 2013 +0000
+++ b/jdk/src/share/classes/java/util/IdentityHashMap.java	Wed Feb 13 14:50:14 2013 -0800
@@ -25,6 +25,7 @@
 
 package java.util;
 import java.io.*;
+import java.lang.reflect.Array;
 
 /**
  * This class implements the <tt>Map</tt> interface with a hash table, using
@@ -1010,6 +1011,37 @@
                 result += System.identityHashCode(key);
             return result;
         }
+        public Object[] toArray() {
+            return toArray(new Object[size()]);
+        }
+        @SuppressWarnings("unchecked")
+        public <T> T[] toArray(T[] a) {
+            int expectedModCount = modCount;
+            int size = size();
+            if (a.length < size)
+                a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
+            Object[] tab = table;
+            int ti = 0;
+            for (int si = 0; si < tab.length; si += 2) {
+                Object key;
+                if ((key = tab[si]) != null) { // key present ?
+                    // more elements than expected -> concurrent modification from other thread
+                    if (ti >= size) {
+                        throw new ConcurrentModificationException();
+                    }
+                    a[ti++] = (T) unmaskNull(key); // unmask key
+                }
+            }
+            // fewer elements than expected or concurrent modification from other thread detected
+            if (ti < size || expectedModCount != modCount) {
+                throw new ConcurrentModificationException();
+            }
+            // final null marker as per spec
+            if (ti < a.length) {
+                a[ti] = null;
+            }
+            return a;
+        }
     }
 
     /**
@@ -1062,6 +1094,36 @@
         public void clear() {
             IdentityHashMap.this.clear();
         }
+        public Object[] toArray() {
+            return toArray(new Object[size()]);
+        }
+        @SuppressWarnings("unchecked")
+        public <T> T[] toArray(T[] a) {
+            int expectedModCount = modCount;
+            int size = size();
+            if (a.length < size)
+                a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
+            Object[] tab = table;
+            int ti = 0;
+            for (int si = 0; si < tab.length; si += 2) {
+                if (tab[si++] != null) { // key present ?
+                    // more elements than expected -> concurrent modification from other thread
+                    if (ti >= size) {
+                        throw new ConcurrentModificationException();
+                    }
+                    a[ti++] = (T) tab[si]; // copy value
+                }
+            }
+            // fewer elements than expected or concurrent modification from other thread detected
+            if (ti < size || expectedModCount != modCount) {
+                throw new ConcurrentModificationException();
+            }
+            // final null marker as per spec
+            if (ti < a.length) {
+                a[ti] = null;
+            }
+            return a;
+        }
     }
 
     /**
@@ -1149,25 +1211,35 @@
         }
 
         public Object[] toArray() {
-            int size = size();
-            Object[] result = new Object[size];
-            Iterator<Map.Entry<K,V>> it = iterator();
-            for (int i = 0; i < size; i++)
-                result[i] = new AbstractMap.SimpleEntry<>(it.next());
-            return result;
+            return toArray(new Object[size()]);
         }
 
         @SuppressWarnings("unchecked")
         public <T> T[] toArray(T[] a) {
+            int expectedModCount = modCount;
             int size = size();
             if (a.length < size)
-                a = (T[])java.lang.reflect.Array
-                    .newInstance(a.getClass().getComponentType(), size);
-            Iterator<Map.Entry<K,V>> it = iterator();
-            for (int i = 0; i < size; i++)
-                a[i] = (T) new AbstractMap.SimpleEntry<>(it.next());
-            if (a.length > size)
-                a[size] = null;
+                a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
+            Object[] tab = table;
+            int ti = 0;
+            for (int si = 0; si < tab.length; si += 2) {
+                Object key;
+                if ((key = tab[si]) != null) { // key present ?
+                    // more elements than expected -> concurrent modification from other thread
+                    if (ti >= size) {
+                        throw new ConcurrentModificationException();
+                    }
+                    a[ti++] = (T) new AbstractMap.SimpleEntry(unmaskNull(key), tab[si + 1]);
+                }
+            }
+            // fewer elements than expected or concurrent modification from other thread detected
+            if (ti < size || expectedModCount != modCount) {
+                throw new ConcurrentModificationException();
+            }
+            // final null marker as per spec
+            if (ti < a.length) {
+                a[ti] = null;
+            }
             return a;
         }
     }