| /* |
| * Copyright (c) 2004, 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 |
| * 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 build.tools.charsetmapping; |
| |
| import java.io.*; |
| import java.util.*; |
| |
| |
| /** |
| * Reads a map in the form of a sequence of key/value-expression pairs from the |
| * standard input, attempts to construct a hash map that fits within the given |
| * table-size and chain-depth constraints, and, if successful, writes source |
| * code to the standard output for a subclass of sun.util.PreHashedMap that |
| * implements the map. |
| * |
| * @see sun.util.PreHashedMap |
| * |
| * @author Mark Reinhold |
| */ |
| |
| public class Hasher { |
| |
| private PrintStream err = System.err; |
| |
| boolean verbose = false; |
| List<String> keys = new ArrayList<>(); // Key strings |
| List<String> values = new ArrayList<>(); // Value expressions |
| String pkg = null; // Package prefix for generated class |
| String cln = null; // Name of generated class |
| String vtype = null; // Value type |
| int maxBits = 11; // lg table size |
| int maxDepth = 3; // Max chain depth |
| boolean inner = false; // Generating an inner class? |
| boolean empty = false; // Generating an empty table? |
| |
| Object[] ht; // Hash table itself |
| int nb; // Number of bits (lg table size) |
| int md; // Maximum chain depth |
| int mask; // Hash-code mask |
| int shift; // Hash-code shift size |
| |
| int hash(String w) { |
| return (w.hashCode() >> shift) & mask; |
| } |
| |
| // Build a hash table of size 2^nb, shifting the hash code by s bits |
| // |
| void build(int nb, int s) { |
| |
| this.nb = nb; |
| this.shift = s; |
| int n = 1 << nb; |
| this.mask = n - 1; |
| ht = new Object[n]; |
| int nw = keys.size(); |
| |
| for (int i = 0; i < nw; i++) { |
| String w = keys.get(i); |
| String v = values.get(i); |
| int h = hash(w); |
| if (ht[h] == null) |
| ht[h] = new Object[] { w, v }; |
| else |
| ht[h] = new Object[] { w, v, ht[h] }; |
| } |
| |
| this.md = 0; |
| for (int i = 0; i < n; i++) { |
| int d = 1; |
| for (Object[] a = (Object[])ht[i]; |
| a != null && a.length > 2; |
| a = (Object[])a[2], d++); |
| this.md = Math.max(md, d); |
| } |
| |
| } |
| |
| Hasher build() { |
| // Iterate through acceptable table sizes |
| for (int nb = 2; nb < maxBits; nb++) { |
| // Iterate through possible shift sizes |
| for (int s = 0; s < (32 - nb); s++) { |
| build(nb, s); |
| if (verbose) |
| err.println("nb=" + nb + " s=" + s + " md=" + md); |
| if (md <= maxDepth) { |
| // Success |
| if (verbose) { |
| if (cln != null) |
| err.print(cln + ": "); |
| err.println("Table size " + (1 << nb) + " (" + nb + " bits)" |
| + ", shift " + shift |
| + ", max chain depth " + md); |
| } |
| return this; |
| } |
| } |
| } |
| throw new RuntimeException("Cannot find a suitable size" |
| + " within given constraints"); |
| } |
| |
| // Look for the given key in the hash table |
| // |
| String get(String k) { |
| int h = hash(k); |
| Object[] a = (Object[])ht[h]; |
| for (;;) { |
| if (a[0].equals(k)) |
| return (String)a[1]; |
| if (a.length < 3) |
| return null; |
| a = (Object[])a[2]; |
| } |
| } |
| |
| // Test that all input keys can be found in the table |
| // |
| Hasher test() { |
| if (verbose) |
| err.println(); |
| for (int i = 0, n = keys.size(); i < n; i++) { |
| String w = keys.get(i); |
| String v = get(w); |
| if (verbose) |
| err.println(hash(w) + "\t" + w); |
| if (!v.equals(values.get(i))) |
| throw new Error("Incorrect value: " + w + " --> " |
| + v + ", should be " + values.get(i)); |
| } |
| return this; |
| } |
| |
| String ind = ""; // Indent prefix |
| |
| // Generate code for a single table entry |
| // |
| void genEntry(Object[] a, int depth, PrintStream out) { |
| Object v = empty ? null : a[1]; |
| out.print("new Object[] { \"" + a[0] + "\", " + v); |
| if (a.length < 3) { |
| out.print(" }"); |
| return; |
| } |
| out.println(","); |
| out.print(ind + " "); |
| for (int i = 0; i < depth; i++) |
| out.print(" "); |
| genEntry((Object[])a[2], depth + 1, out); |
| out.print(" }"); |
| } |
| |
| // Generate a PreHashedMap subclass from the computed hash table |
| // |
| Hasher generate(PrintStream out) throws IOException { |
| if (cln == null) |
| return this; |
| |
| if (inner) |
| ind = " "; |
| |
| if (!inner && pkg != null) { |
| out.println(); |
| out.println("package " + pkg + ";"); |
| out.println(); |
| } |
| |
| if (inner) { |
| out.println(ind + "private static final class " + cln); |
| } else { |
| out.println(); |
| out.println("public final class " + cln); |
| } |
| out.println(ind + " extends sun.util.PreHashedMap<" + vtype +">"); |
| out.println(ind + "{"); |
| |
| out.println(); |
| out.println(ind + " private static final int ROWS = " |
| + ht.length + ";"); |
| out.println(ind + " private static final int SIZE = " |
| + keys.size() + ";"); |
| out.println(ind + " private static final int SHIFT = " |
| + shift + ";"); |
| out.println(ind + " private static final int MASK = 0x" |
| + Integer.toHexString(mask) + ";"); |
| out.println(); |
| |
| out.println(ind + " " + (inner ? "private " : "public ") |
| + cln + "() {"); |
| out.println(ind + " super(ROWS, SIZE, SHIFT, MASK);"); |
| out.println(ind + " }"); |
| out.println(); |
| |
| out.println(ind + " protected void init(Object[] ht) {"); |
| for (int i = 0; i < ht.length; i++) { |
| if (ht[i] == null) |
| continue; |
| Object[] a = (Object[])ht[i]; |
| out.print(ind + " ht[" + i + "] = "); |
| genEntry(a, 0, out); |
| out.println(";"); |
| } |
| out.println(ind + " }"); |
| out.println(); |
| |
| out.println(ind + "}"); |
| if (inner) |
| out.println(); |
| |
| return this; |
| } |
| |
| private Hasher(List<String> keys, List<String> values, |
| String pkg, String cln, String vtype, |
| int maxBits, int maxDepth, |
| boolean inner, boolean empty, |
| boolean verbose) { |
| this.keys = keys; |
| this.values = values; |
| this.pkg = pkg; |
| this.cln = cln; |
| this.vtype = vtype; |
| this.maxBits = maxBits; |
| this.maxDepth = maxDepth; |
| this.inner = inner; |
| this.empty = empty; |
| this.verbose = verbose; |
| } |
| |
| public static void genClass(PrintStream out, |
| List<String> keys, List<String> values, |
| String pkg, String cln, String vtype, |
| int maxBits, int maxDepth, |
| boolean inner, boolean empty, boolean verbose) |
| throws IOException { |
| new Hasher(keys, values, pkg, cln, vtype, |
| maxBits, maxDepth, inner, empty, verbose) |
| .build() |
| .test() |
| .generate(out); |
| } |
| } |