|
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 |
|
26 package build.tools.hasher; |
|
27 |
|
28 import java.io.*; |
|
29 import 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 |
|
44 public 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 } |