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.hasher;
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    static final PrintStream out = System.out;
47    static final PrintStream err = System.err;
48
49    boolean verbose = false;
50
51    List<String> keys = new ArrayList<>();      // Key strings
52    List<String> values = new ArrayList<>();    // Value expressions
53    String pkg = null;                          // Package prefix for generated class
54    String cln = null;                          // Name of generated class
55    String vtype = "String";                    // Value type
56    int maxBits = 11;                           // lg table size
57    int maxDepth = 3;                           // Max chain depth
58    boolean inner = false;                      // Generating an inner class?
59    boolean empty = false;                      // Generating an empty table?
60
61    void usage() {
62        err.println("usage: java Hasher [options] [[pkgName.]ClassName]");
63        err.println("options:");
64        err.println("    -e           generate empty table (ignores value exprs)");
65        err.println("    -i           generate a static inner class");
66        err.println("    -md depth    max chain depth (default 3)");
67        err.println("    -mb bits     max index bits (lg of table size, default 10)");
68        err.println("    -t type      value type (default String)");
69        err.println("    -v           verbose");
70        err.println("Key/value-expression pairs are read from standard input");
71        err.println("If class name is given then source is written to standard output");
72        System.exit(1);
73    }
74
75    Hasher(String[] args) {
76        List<String> as = Arrays.asList(args);
77        for (Iterator<String> i = as.iterator(); i.hasNext();) {
78            String a = i.next();
79            if (a.equals("-e")) {
80                empty = true;
81            } else if (a.equals("-i")) {
82                inner = true;
83            } else if (a.equals("-v")) {
84                verbose = true;
85            } else if (a.equals("-md")) {
86                if (!i.hasNext())
87                    usage();
88                maxDepth = Integer.parseInt(i.next());
89            } else if (a.equals("-mb")) {
90                if (!i.hasNext())
91                    usage();
92                maxBits = Integer.parseInt(i.next());
93            } else if (a.equals("-t")) {
94                if (!i.hasNext())
95                    usage();
96                vtype = i.next();
97            } else if (a.startsWith("-")) {
98                usage();
99            } else {
100                int j = a.lastIndexOf('.');
101                if (j >= 0) {
102                    pkg = a.substring(0, j);
103                    cln = a.substring(j + 1);
104                } else {
105                    cln = a;
106                }
107            }
108        }
109        if (verbose)
110            err.println("pkg=" + pkg + ", cln=" + cln);
111    }
112
113    // Read keys and values
114    //
115    Hasher load() throws IOException {
116        BufferedReader br
117            = new BufferedReader(new InputStreamReader(System.in));
118        for (String ln; (ln = br.readLine()) != null;) {
119            String[] ws = ln.split(",?\\s+", 2);
120            String w = ws[0].replaceAll("\"", "");
121            if (keys.contains(w))
122                throw new RuntimeException("Duplicate word in input: " + w);
123            keys.add(w);
124            if (ws.length < 2)
125                throw new RuntimeException("Missing expression for key " + w);
126            values.add(ws[1]);
127        }
128        return this;
129    }
130
131    Object[] ht;                        // Hash table itself
132    int nb;                             // Number of bits (lg table size)
133    int md;                             // Maximum chain depth
134    int mask;                           // Hash-code mask
135    int shift;                          // Hash-code shift size
136
137    int hash(String w) {
138        return (w.hashCode() >> shift) & mask;
139    }
140
141    // Build a hash table of size 2^nb, shifting the hash code by s bits
142    //
143    void build(int nb, int s) {
144
145        this.nb = nb;
146        this.shift = s;
147        int n = 1 << nb;
148        this.mask = n - 1;
149        ht = new Object[n];
150        int nw = keys.size();
151
152        for (int i = 0; i < nw; i++) {
153            String w = keys.get(i);
154            String v = values.get(i);
155            int h = hash(w);
156            if (ht[h] == null)
157                ht[h] = new Object[] { w, v };
158            else
159                ht[h] = new Object[] { w, v, ht[h] };
160        }
161
162        this.md = 0;
163        for (int i = 0; i < n; i++) {
164            int d = 1;
165            for (Object[] a = (Object[])ht[i];
166                 a != null && a.length > 2;
167                 a = (Object[])a[2], d++);
168            this.md = Math.max(md, d);
169        }
170
171    }
172
173    Hasher build() {
174        // Iterate through acceptable table sizes
175        for (int nb = 2; nb < maxBits; nb++) {
176            // Iterate through possible shift sizes
177            for (int s = 0; s < (32 - nb); s++) {
178                build(nb, s);
179                if (verbose)
180                    err.println("nb=" + nb + " s=" + s + " md=" + md);
181                if (md <= maxDepth) {
182                    // Success
183                    out.flush();
184                    if (verbose) {
185                        if (cln != null)
186                            err.print(cln + ": ");
187                        err.println("Table size " + (1 << nb) + " (" + nb + " bits)"
188                                    + ", shift " + shift
189                                    + ", max chain depth " + md);
190                    }
191                    return this;
192                }
193            }
194        }
195        throw new RuntimeException("Cannot find a suitable size"
196                                   + " within given constraints");
197    }
198
199    // Look for the given key in the hash table
200    //
201    String get(String k) {
202        int h = hash(k);
203        Object[] a = (Object[])ht[h];
204        for (;;) {
205            if (a[0].equals(k))
206                return (String)a[1];
207            if (a.length < 3)
208                return null;
209            a = (Object[])a[2];
210        }
211    }
212
213    // Test that all input keys can be found in the table
214    //
215    Hasher test() {
216        if (verbose)
217            err.println();
218        for (int i = 0, n = keys.size(); i < n; i++) {
219            String w = keys.get(i);
220            String v = get(w);
221            if (verbose)
222                err.println(hash(w) + "\t" + w);
223            if (!v.equals(values.get(i)))
224                throw new Error("Incorrect value: " + w + " --> "
225                                + v + ", should be " + values.get(i));
226        }
227        return this;
228    }
229
230    String ind = "";                    // Indent prefix
231
232    // Generate code for a single table entry
233    //
234    void genEntry(Object[] a, int depth, PrintWriter pw) {
235        Object v = empty ? null : a[1];
236        pw.print("new Object[] { \"" + a[0] + "\", " + v);
237        if (a.length < 3) {
238            pw.print(" }");
239            return;
240        }
241        pw.println(",");
242        pw.print(ind + "                     ");
243        for (int i = 0; i < depth; i++)
244            pw.print("    ");
245        genEntry((Object[])a[2], depth + 1, pw);
246        pw.print(" }");
247    }
248
249    // Generate a PreHashedMap subclass from the computed hash table
250    //
251    Hasher generate() throws IOException {
252        if (cln == null)
253            return this;
254        PrintWriter pw
255            = new PrintWriter(new BufferedWriter(new OutputStreamWriter(out)));
256
257        if (inner)
258            ind = "    ";
259
260        if (!inner && pkg != null) {
261            pw.println();
262            pw.println("package " + pkg + ";");
263            pw.println();
264        }
265
266        if (inner) {
267            pw.println(ind + "private static final class " + cln);
268        } else {
269            pw.println();
270            pw.println("public final class " + cln);
271        }
272        pw.println(ind + "    extends sun.util.PreHashedMap<" + vtype +">");
273        pw.println(ind + "{");
274
275        pw.println();
276        pw.println(ind + "    private static final int ROWS = "
277                   + ht.length + ";");
278        pw.println(ind + "    private static final int SIZE = "
279                   + keys.size() + ";");
280        pw.println(ind + "    private static final int SHIFT = "
281                   + shift + ";");
282        pw.println(ind + "    private static final int MASK = 0x"
283                   + Integer.toHexString(mask) + ";");
284        pw.println();
285
286        pw.println(ind + "    " + (inner ? "private " : "public ")
287                   + cln + "() {");
288        pw.println(ind + "        super(ROWS, SIZE, SHIFT, MASK);");
289        pw.println(ind + "    }");
290        pw.println();
291
292        pw.println(ind + "    protected void init(Object[] ht) {");
293        for (int i = 0; i < ht.length; i++) {
294            if (ht[i] == null)
295                continue;
296            Object[] a = (Object[])ht[i];
297            pw.print(ind + "        ht[" + i + "] = ");
298            genEntry(a, 0, pw);
299            pw.println(";");
300        }
301        pw.println(ind + "    }");
302        pw.println();
303
304        pw.println(ind + "}");
305        if (inner)
306            pw.println();
307
308        pw.close();
309        return this;
310    }
311
312    public static void main(String[] args) throws IOException {
313        new Hasher(args)
314            .load()
315            .build()
316            .test()
317            .generate();
318    }
319
320}
321