harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From telli...@apache.org
Subject svn commit: r509249 - in /harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util: HashMap.java LinkedHashMap.java
Date Mon, 19 Feb 2007 16:42:52 GMT
Author: tellison
Date: Mon Feb 19 08:42:52 2007
New Revision: 509249

URL: http://svn.apache.org/viewvc?view=rev&rev=509249
Log:
Apply patch HARMONY-642 (Performance improvement for HashMap and LinkedHashMap classes)

Modified:
    harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/HashMap.java
    harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/LinkedHashMap.java

Modified: harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/HashMap.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/HashMap.java?view=diff&rev=509249&r1=509248&r2=509249
==============================================================================
--- harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/HashMap.java (original)
+++ harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/HashMap.java Mon
Feb 19 08:42:52 2007
@@ -47,6 +47,11 @@
 
         Entry<K, V> next;
 
+        Entry(K theKey, int hash) {
+            super(theKey, null);
+            this.origKeyHash = hash;
+        }
+
         Entry(K theKey, V theValue) {
             super(theKey, theValue);
             origKeyHash = (theKey == null ? 0 : theKey.hashCode());
@@ -180,8 +185,15 @@
         @Override
         public boolean contains(Object object) {
             if (object instanceof Map.Entry) {
-                Entry<KT, VT> entry = associatedMap
-                        .getEntry(((Map.Entry<?, ?>) object).getKey());
+                Object key = ((Map.Entry<?, ?>) object).getKey();
+                Entry entry;
+                if (key == null) {
+                    entry = associatedMap.findNullKeyEntry();
+                } else {
+                    int hash = key.hashCode();
+                    int index = (hash & 0x7FFFFFFF) % associatedMap.elementData.length;
+                    entry = associatedMap.findNonNullKeyEntry(key, index, hash);
+                }
                 return object.equals(entry);
             }
             return false;
@@ -328,29 +340,15 @@
      */
     @Override
     public boolean containsKey(Object key) {
-        return getEntry(key) != null;
-    }
-
-    /**
-     * Tests two keys for equality. This method just calls key.equals but can be
-     * overridden.
-     * 
-     * @param k1
-     *            first key to compare
-     * @param k2
-     *            second key to compare
-     * @return true if the keys are considered equal
-     */
-    boolean keysEqual(Object k1, Entry<K, V> entry) {
-        int k1Hash = k1 == null ? 0 : k1.hashCode();
-        if (k1Hash != entry.origKeyHash) {
-            return false;
-        }
-        if (k1 == null && entry.key == null) {
-            return true;
+        Entry<K, V> m;
+        if (key == null) {
+            m = findNullKeyEntry();
+        } else {
+            int hash = key.hashCode();
+            int index = (hash & 0x7FFFFFFF) % elementData.length;
+            m = findNonNullKeyEntry(key, index, hash);
         }
-        assert k1 != null;
-        return k1.equals(entry.key);
+        return m != null;
     }
 
     /**
@@ -408,37 +406,32 @@
      */
     @Override
     public V get(Object key) {
-        Entry<K, V> m = getEntry(key);
+        Entry<K, V> m;
+        if (key == null) {
+            m = findNullKeyEntry();
+        } else {
+            int hash = key.hashCode();
+            int index = (hash & 0x7FFFFFFF) % elementData.length;
+            m = findNonNullKeyEntry(key, index, hash);
+        }
         if (m != null) {
             return m.value;
         }
         return null;
     }
 
-    Entry<K, V> getEntry(Object key) {
-        int index = getModuloHash(key);
-        return findEntry(key, index);
-    }
-
-    int getModuloHash(Object key) {
-        if (key == null) {
-            return 0;
+    final Entry<K,V> findNonNullKeyEntry(Object key, int index, int keyHash) {
+        Entry<K,V> m = elementData[index];
+        while (m != null && (m.origKeyHash != keyHash || !key.equals(m.key))) {
+            m = m.next;
         }
-        return (key.hashCode() & 0x7FFFFFFF) % elementData.length;
+        return m;
     }
-
-    Entry<K, V> findEntry(Object key, int index) {
-        Entry<K, V> m;
-        m = elementData[index];
-        if (key != null) {
-            while (m != null && !keysEqual(key, m)) {
-                m = m.next;
-            }
-        } else {
-            while (m != null && m.key != null) {
-                m = m.next;
-            }
-        }
+  
+    final Entry<K,V> findNullKeyEntry() {
+        Entry<K,V> m = elementData[0];
+        while (m != null && m.key != null)
+            m = m.next;
         return m;
     }
 
@@ -482,11 +475,8 @@
 
                 @Override
                 public boolean remove(Object key) {
-                    if (containsKey(key)) {
-                        HashMap.this.remove(key);
-                        return true;
-                    }
-                    return false;
+                    Entry<K, V> entry = HashMap.this.removeEntry(key);
+                    return entry != null;
                 }
 
                 @Override
@@ -519,18 +509,28 @@
     }
 
     private V putImpl(K key, V value) {
-        int index = getModuloHash(key);
-        Entry<K, V> entry = findEntry(key, index);
-
-        if (entry == null) {
-            modCount++;
-            if (++elementCount > threshold) {
-                rehash();
-                index = key == null ? 0 : (key.hashCode() & 0x7FFFFFFF)
-                        % elementData.length;
+        Entry<K,V> entry;
+        if(key == null) {
+            entry = findNullKeyEntry();
+            if (entry == null) {
+                modCount++;
+                if (++elementCount > threshold) {
+                    rehash();
+                }
+                entry = createHashedEntry(key, 0, 0);
+            }
+        } else {
+            int hash = key.hashCode();
+            int index = (hash & 0x7FFFFFFF) % elementData.length;
+            entry = findNonNullKeyEntry(key, index, hash);
+            if (entry == null) {
+                modCount++;
+                if (++elementCount > threshold) {
+                    rehash();
+                    index = (hash & 0x7FFFFFFF) % elementData.length;
+                }
+                entry = createHashedEntry(key, index, hash);
             }
-            createEntry(key, index, value);
-            return null;
         }
 
         V result = entry.value;
@@ -545,6 +545,13 @@
         return entry;
     }
 
+    Entry<K,V> createHashedEntry(K key, int index, int hash) {
+        Entry<K,V> entry = new Entry<K,V>(key,hash);
+        entry.next = elementData[index];
+        elementData[index] = entry;
+        return entry;
+    }
+
     /**
      * Copies all the mappings in the given map to this map. These mappings will
      * replace all mappings that this map had for any of the keys currently in
@@ -579,9 +586,7 @@
         for (int i = 0; i < elementData.length; i++) {
             Entry<K, V> entry = elementData[i];
             while (entry != null) {
-                Object key = entry.key;
-                int index = key == null ? 0 : (key.hashCode() & 0x7FFFFFFF)
-                        % length;
+                int index = (entry.origKeyHash & 0x7FFFFFFF) % length;
                 Entry<K, V> next = entry.next;
                 entry.next = newData[index];
                 newData[index] = entry;
@@ -618,9 +623,10 @@
         Entry<K, V> entry;
         Entry<K, V> last = null;
         if (key != null) {
-            index = (key.hashCode() & 0x7FFFFFFF) % elementData.length;
+            int hash = key.hashCode();
+            index = (hash & 0x7FFFFFFF) % elementData.length;
             entry = elementData[index];
-            while (entry != null && !keysEqual(key, entry)) {
+            while (entry != null && !(entry.origKeyHash == hash && key.equals(entry.key)))
{
                 last = entry;
                 entry = entry.next;
             }

Modified: harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/LinkedHashMap.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/LinkedHashMap.java?view=diff&rev=509249&r1=509248&r2=509249
==============================================================================
--- harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/LinkedHashMap.java
(original)
+++ harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/LinkedHashMap.java
Mon Feb 19 08:42:52 2007
@@ -139,7 +139,7 @@
             canRemove = false;
             associatedMap.modCount++;
 
-            int index = associatedMap.getModuloHash(lastEntry.key);
+            int index = (lastEntry.key == null)? 0 : (lastEntry.key.hashCode() & 0x7FFFFFFF)
% associatedMap.elementData.length;
             LinkedHashMapEntry<KT, VT> m = (LinkedHashMapEntry<KT, VT>) associatedMap.elementData[index];
             if (m == lastEntry) {
                 associatedMap.elementData[index] = lastEntry.next;
@@ -201,6 +201,13 @@
             chainBackward = null;
         }
 
+        LinkedHashMapEntry(K theKey, int hash) {
+            super(theKey, hash);
+            chainForward = null;
+            chainBackward = null;
+        }
+
+
         @Override
         @SuppressWarnings("unchecked")
         public Object clone() {
@@ -236,7 +243,14 @@
      */
     @Override
     public V get(Object key) {
-        LinkedHashMapEntry<K, V> m = (LinkedHashMapEntry<K, V>) getEntry(key);
+        LinkedHashMapEntry<K, V> m;
+        if (key == null) {
+            m = (LinkedHashMapEntry<K, V>)findNullKeyEntry();
+        } else {
+            int hash = key.hashCode();
+            int index = (hash & 0x7FFFFFFF) % elementData.length;
+            m = (LinkedHashMapEntry<K, V>)findNonNullKeyEntry(key, index, hash);
+        }
         if (m == null) {
             return null;
         }
@@ -269,6 +283,14 @@
         return m;
     }
 
+    Entry<K,V> createHashedEntry(K key, int index, int hash) {
+        LinkedHashMapEntry<K, V> m = new LinkedHashMapEntry<K, V>(key, hash);
+        m.next = elementData[index];
+        elementData[index] = m;
+        linkEntry(m);
+        return m;
+    }
+
     /**
      * Set the mapped value for the given key to the given value.
      * 
@@ -281,23 +303,36 @@
      */
     @Override
     public V put(K key, V value) {
-        int index = getModuloHash(key);
-        LinkedHashMapEntry<K, V> m = (LinkedHashMapEntry<K, V>) findEntry(key,
index);
-
-        if (m == null) {
-            modCount++;
-            // Check if we need to remove the oldest entry
-            // The check includes accessOrder since an accessOrder LinkedHashMap
-            // does not record
-            // the oldest member in 'head'.
-            if (++elementCount > threshold) {
-                rehash();
-                index = key == null ? 0 : (key.hashCode() & 0x7FFFFFFF)
-                        % elementData.length;
+        LinkedHashMapEntry<K, V> m;
+        if (key == null) {
+            m = (LinkedHashMapEntry<K, V>)findNullKeyEntry();
+            if (m == null) {
+                modCount++;
+                // Check if we need to remove the oldest entry
+                // The check includes accessOrder since an accessOrder LinkedHashMap
+                // does not record
+                // the oldest member in 'head'.
+                if (++elementCount > threshold) {
+                    rehash();
+                }
+                    m = (LinkedHashMapEntry<K, V>) createHashedEntry(key, 0, 0);
+            } else {
+                linkEntry(m);
             }
-            m = (LinkedHashMapEntry<K, V>) createEntry(key, index, null);
         } else {
-            linkEntry(m);
+            int hash = key.hashCode();
+            int index = (hash & 0x7FFFFFFF) % elementData.length;
+            m = (LinkedHashMapEntry<K, V>)findNonNullKeyEntry(key, index, hash);
+            if (m == null) {
+                modCount++;
+                if (++elementCount > threshold) {
+                    rehash();
+                    index = (hash & 0x7FFFFFFF) % elementData.length;
+                }
+                m = (LinkedHashMapEntry<K, V>) createHashedEntry(key, index, hash);
+            } else {
+                linkEntry(m);
+            }
         }
 
         V result = m.value;



Mime
View raw message