changeset 3226:1514b395e8e1

8033287: Reduce the size of the endPosTable Reviewed-by: jjg Contributed-by: per.bothner@oracle.com, chturne@gmail.com
author jjg
date Thu, 27 Feb 2014 13:57:57 -0800
parents b03893804cd3
children 35789cbea856
files src/share/classes/com/sun/tools/javac/parser/JavacParser.java src/share/classes/com/sun/tools/javac/util/IntHashTable.java
diffstat 2 files changed, 208 insertions(+), 8 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/com/sun/tools/javac/parser/JavacParser.java	Thu Feb 27 11:47:39 2014 -0800
+++ b/src/share/classes/com/sun/tools/javac/parser/JavacParser.java	Thu Feb 27 13:57:57 2014 -0800
@@ -4055,15 +4055,16 @@
      */
     protected static class SimpleEndPosTable extends AbstractEndPosTable {
 
-        private final Map<JCTree, Integer> endPosMap;
+        private final IntHashTable endPosMap;
 
         SimpleEndPosTable(JavacParser parser) {
             super(parser);
-            endPosMap = new HashMap<>();
+            endPosMap = new IntHashTable();
         }
 
         public void storeEnd(JCTree tree, int endpos) {
-            endPosMap.put(tree, errorEndPos > endpos ? errorEndPos : endpos);
+            endPosMap.putAtIndex(tree, errorEndPos > endpos ? errorEndPos : endpos,
+                                 endPosMap.lookup(tree));
         }
 
         protected <T extends JCTree> T to(T t) {
@@ -4077,14 +4078,15 @@
         }
 
         public int getEndPos(JCTree tree) {
-            Integer value = endPosMap.get(tree);
-            return (value == null) ? Position.NOPOS : value;
+            int value = endPosMap.getFromIndex(endPosMap.lookup(tree));
+            // As long as Position.NOPOS==-1, this just returns value.
+            return (value == -1) ? Position.NOPOS : value;
         }
 
         public int replaceTree(JCTree oldTree, JCTree newTree) {
-            Integer pos = endPosMap.remove(oldTree);
-            if (pos != null) {
-                endPosMap.put(newTree, pos);
+            int pos = endPosMap.remove(oldTree);
+            if (pos != -1) {
+                storeEnd(newTree, pos);
                 return pos;
             }
             return Position.NOPOS;
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/share/classes/com/sun/tools/javac/util/IntHashTable.java	Thu Feb 27 13:57:57 2014 -0800
@@ -0,0 +1,198 @@
+/*
+ * Copyright (c) 2014, 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 com.sun.tools.javac.util;
+
+/**
+ * A hash table that maps Object to int.
+ *
+ * This is a custom hash table optimised for the Object -> int
+ * maps. This is done to avoid unnecessary object allocation in the image set.
+ *
+ * @author Charles Turner
+ * @author Per Bothner
+ */
+public class IntHashTable {
+    private static final int DEFAULT_INITIAL_SIZE = 64;
+    protected Object[] objs; // the domain set
+    protected int[] ints; // the image set
+    protected int mask; // used to clip int's into the domain
+    protected int num_bindings; // the number of mappings (including DELETED)
+    private final static Object DELETED = new Object();
+
+    /**
+     * Construct an Object -> int hash table.
+     *
+     * The default size of the hash table is 64 mappings.
+     */
+    public IntHashTable() {
+        objs = new Object[DEFAULT_INITIAL_SIZE];
+        ints = new int[DEFAULT_INITIAL_SIZE];
+        mask = DEFAULT_INITIAL_SIZE - 1;
+    }
+
+    /**
+     * Construct an Object -> int hash table with a specified amount of mappings.
+     * @param capacity The number of default mappings in this hash table.
+     */
+    public IntHashTable(int capacity) {
+        int log2Size = 4;
+        while (capacity > (1 << log2Size)) {
+            log2Size++;
+        }
+        capacity = 1 << log2Size;
+        objs = new Object[capacity];
+        ints = new int[capacity];
+        mask = capacity - 1;
+    }
+
+    /**
+     * Compute the hash code of a given object.
+     *
+     * @param key The object whose hash code is to be computed.
+     * @return zero if the object is null, otherwise the identityHashCode
+     */
+    public int hash(Object key) {
+        return System.identityHashCode(key);
+    }
+
+    /**
+     * Find either the index of a key's value, or the index of an available space.
+     *
+     * @param key The key to whose value you want to find.
+     * @param hash The hash code of this key.
+     * @return Either the index of the key's value, or an index pointing to
+     * unoccupied space.
+     */
+    public int lookup(Object key, int hash) {
+        Object node;
+        int hash1 = hash ^ (hash >>> 15);
+        int hash2 = (hash ^ (hash << 6)) | 1; //ensure coprimeness
+        int deleted = -1;
+        for (int i = hash1 & mask;; i = (i + hash2) & mask) {
+            node = objs[i];
+            if (node == key)
+                return i;
+            if (node == null)
+                return deleted >= 0 ? deleted : i;
+            if (node == DELETED && deleted < 0)
+                deleted = i;
+        }
+    }
+
+    /**
+     * Lookup a given key's value in the hash table.
+     *
+     * @param key The key whose value you want to find.
+     * @return Either the index of the key's value, or an index pointing to
+     * unoccupied space.
+     */
+    public int lookup(Object key) {
+        return lookup(key, hash(key));
+    }
+
+    /**
+     * Return the value stored at the specified index in the table.
+     *
+     * @param index The index to inspect, as returned from {@link #lookup}
+     * @return A non-negative integer if the index contains a non-null
+     *         value, or -1 if it does.
+     */
+    public int getFromIndex(int index) {
+        Object node = objs[index];
+        return node == null || node == DELETED ? -1 : ints[index];
+    }
+
+    /**
+     * Associates the specified key with the specified value in this map.
+     *
+     * @param key key with which the specified value is to be associated.
+     * @param value value to be associated with the specified key.
+     * @param index the index at which to place this binding, as returned
+     *              from {@link #lookup}.
+     * @return previous value associated with specified key, or -1 if there was
+     * no mapping for key.
+     */
+    public int putAtIndex(Object key, int value, int index) {
+        Object old = objs[index];
+        if (old == null || old == DELETED) {
+            objs[index] = key;
+            ints[index] = value;
+            if (old != DELETED)
+                num_bindings++;
+            if (3 * num_bindings >= 2 * objs.length)
+                rehash();
+            return -1;
+        } else { // update existing mapping
+            int oldValue = ints[index];
+            ints[index] = value;
+            return oldValue;
+        }
+    }
+
+    public int remove(Object key) {
+        int index = lookup(key);
+        Object old = objs[index];
+        if (old == null || old == DELETED)
+            return -1;
+        objs[index] = DELETED;
+        return ints[index];
+    }
+
+    /**
+     * Expand the hash table when it exceeds the load factor.
+     *
+     * Rehash the existing objects.
+     */
+    protected void rehash() {
+        Object[] oldObjsTable = objs;
+        int[] oldIntsTable = ints;
+        int oldCapacity = oldObjsTable.length;
+        int newCapacity = oldCapacity << 1;
+        Object[] newObjTable = new Object[newCapacity];
+        int[] newIntTable = new int[newCapacity];
+        int newMask = newCapacity - 1;
+        objs = newObjTable;
+        ints = newIntTable;
+        mask = newMask;
+        num_bindings = 0; // this is recomputed below
+        Object key;
+        for (int i = oldIntsTable.length; --i >= 0;) {
+            key = oldObjsTable[i];
+            if (key != null && key != DELETED)
+                putAtIndex(key, oldIntsTable[i], lookup(key, hash(key)));
+        }
+    }
+
+    /**
+     * Removes all mappings from this map.
+     */
+    public void clear() {
+        for (int i = objs.length; --i >= 0;) {
+            objs[i] = null;
+        }
+        num_bindings = 0;
+    }
+}