1/*
2 * Copyright (c) 2004, 2013, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.  Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26package build.tools.charsetmapping;
27
28import java.io.*;
29import java.util.*;
30
31
32/**
33 * Reads a map in the form of a sequence of key/value-expression pairs from the
34 * standard input, attempts to construct a hash map that fits within the given
35 * table-size and chain-depth constraints, and, if successful, writes source
36 * code to the standard output for a subclass of sun.util.PreHashedMap that
37 * implements the map.
38 *
39 * @see sun.util.PreHashedMap
40 *
41 * @author Mark Reinhold
42 */
43
44public class Hasher {
45
46    private PrintStream err = System.err;
47
48    boolean verbose = false;
49    List<String> keys = new ArrayList<>();      // Key strings
50    List<String> values = new ArrayList<>();    // Value expressions
51    String pkg = null;                          // Package prefix for generated class
52    String cln = null;                          // Name of generated class
53    String vtype = null;                        // Value type
54    int maxBits = 11;                           // lg table size
55    int maxDepth = 3;                           // Max chain depth
56    boolean inner = false;                      // Generating an inner class?
57    boolean empty = false;                      // Generating an empty table?
58
59    Object[] ht;                                // Hash table itself
60    int nb;                                     // Number of bits (lg table size)
61    int md;                                     // Maximum chain depth
62    int mask;                                   // Hash-code mask
63    int shift;                                  // Hash-code shift size
64
65    int hash(String w) {
66        return (w.hashCode() >> shift) & mask;
67    }
68
69    // Build a hash table of size 2^nb, shifting the hash code by s bits
70    //
71    void build(int nb, int s) {
72
73        this.nb = nb;
74        this.shift = s;
75        int n = 1 << nb;
76        this.mask = n - 1;
77        ht = new Object[n];
78        int nw = keys.size();
79
80        for (int i = 0; i < nw; i++) {
81            String w = keys.get(i);
82            String v = values.get(i);
83            int h = hash(w);
84            if (ht[h] == null)
85                ht[h] = new Object[] { w, v };
86            else
87                ht[h] = new Object[] { w, v, ht[h] };
88        }
89
90        this.md = 0;
91        for (int i = 0; i < n; i++) {
92            int d = 1;
93            for (Object[] a = (Object[])ht[i];
94                 a != null && a.length > 2;
95                 a = (Object[])a[2], d++);
96            this.md = Math.max(md, d);
97        }
98
99    }
100
101    Hasher build() {
102        // Iterate through acceptable table sizes
103        for (int nb = 2; nb < maxBits; nb++) {
104            // Iterate through possible shift sizes
105            for (int s = 0; s < (32 - nb); s++) {
106                build(nb, s);
107                if (verbose)
108                    err.println("nb=" + nb + " s=" + s + " md=" + md);
109                if (md <= maxDepth) {
110                    // Success
111                     if (verbose) {
112                        if (cln != null)
113                            err.print(cln + ": ");
114                        err.println("Table size " + (1 << nb) + " (" + nb + " bits)"
115                                    + ", shift " + shift
116                                    + ", max chain depth " + md);
117                    }
118                    return this;
119                }
120            }
121        }
122        throw new RuntimeException("Cannot find a suitable size"
123                                   + " within given constraints");
124    }
125
126    // Look for the given key in the hash table
127    //
128    String get(String k) {
129        int h = hash(k);
130        Object[] a = (Object[])ht[h];
131        for (;;) {
132            if (a[0].equals(k))
133                return (String)a[1];
134            if (a.length < 3)
135                return null;
136            a = (Object[])a[2];
137        }
138    }
139
140    // Test that all input keys can be found in the table
141    //
142    Hasher test() {
143        if (verbose)
144            err.println();
145        for (int i = 0, n = keys.size(); i < n; i++) {
146            String w = keys.get(i);
147            String v = get(w);
148            if (verbose)
149                err.println(hash(w) + "\t" + w);
150            if (!v.equals(values.get(i)))
151                throw new Error("Incorrect value: " + w + " --> "
152                                + v + ", should be " + values.get(i));
153        }
154        return this;
155    }
156
157    String ind = "";                    // Indent prefix
158
159    // Generate code for a single table entry
160    //
161    void genEntry(Object[] a, int depth, PrintStream out) {
162        Object v = empty ? null : a[1];
163        out.print("new Object[] { \"" + a[0] + "\", " + v);
164        if (a.length < 3) {
165            out.print(" }");
166            return;
167        }
168        out.println(",");
169        out.print(ind + "                     ");
170        for (int i = 0; i < depth; i++)
171            out.print("    ");
172        genEntry((Object[])a[2], depth + 1, out);
173        out.print(" }");
174    }
175
176    // Generate a PreHashedMap subclass from the computed hash table
177    //
178    Hasher generate(PrintStream out) throws IOException {
179        if (cln == null)
180            return this;
181
182        if (inner)
183            ind = "    ";
184
185        if (!inner && pkg != null) {
186            out.println();
187            out.println("package " + pkg + ";");
188            out.println();
189        }
190
191        if (inner) {
192            out.println(ind + "private static final class " + cln);
193        } else {
194            out.println();
195            out.println("public final class " + cln);
196        }
197        out.println(ind + "    extends sun.util.PreHashedMap<" + vtype +">");
198        out.println(ind + "{");
199
200        out.println();
201        out.println(ind + "    private static final int ROWS = "
202                    + ht.length + ";");
203        out.println(ind + "    private static final int SIZE = "
204                    + keys.size() + ";");
205        out.println(ind + "    private static final int SHIFT = "
206                    + shift + ";");
207        out.println(ind + "    private static final int MASK = 0x"
208                    + Integer.toHexString(mask) + ";");
209        out.println();
210
211        out.println(ind + "    " + (inner ? "private " : "public ")
212                    + cln + "() {");
213        out.println(ind + "        super(ROWS, SIZE, SHIFT, MASK);");
214        out.println(ind + "    }");
215        out.println();
216
217        out.println(ind + "    protected void init(Object[] ht) {");
218        for (int i = 0; i < ht.length; i++) {
219            if (ht[i] == null)
220                continue;
221            Object[] a = (Object[])ht[i];
222            out.print(ind + "        ht[" + i + "] = ");
223            genEntry(a, 0, out);
224            out.println(";");
225        }
226        out.println(ind + "    }");
227        out.println();
228
229        out.println(ind + "}");
230        if (inner)
231            out.println();
232
233        return this;
234    }
235
236    private Hasher(List<String> keys, List<String> values,
237                   String pkg, String cln, String vtype,
238                   int maxBits, int maxDepth,
239                   boolean inner, boolean empty,
240                   boolean verbose) {
241        this.keys = keys;
242        this.values = values;
243        this.pkg = pkg;
244        this.cln = cln;
245        this.vtype = vtype;
246        this.maxBits = maxBits;
247        this.maxDepth = maxDepth;
248        this.inner = inner;
249        this.empty = empty;
250        this.verbose = verbose;
251    }
252
253    public static void genClass(PrintStream out,
254                                List<String> keys, List<String> values,
255                                String pkg, String cln, String vtype,
256                                int maxBits, int maxDepth,
257                                boolean inner, boolean empty, boolean verbose)
258        throws IOException {
259        new Hasher(keys, values, pkg, cln, vtype,
260                   maxBits, maxDepth, inner, empty, verbose)
261            .build()
262            .test()
263            .generate(out);
264    }
265}
266