author | jjg |
Thu, 09 Mar 2017 13:46:39 -0800 | |
changeset 44123 | 3a090845d178 |
parent 23010 | 6dadb192ad81 |
permissions | -rw-r--r-- |
2 | 1 |
/* |
23010
6dadb192ad81
8029235: Update copyright year to match last edit in jdk8 jdk repository for 2013
lana
parents:
22639
diff
changeset
|
2 |
* Copyright (c) 2004, 2013, Oracle and/or its affiliates. All rights reserved. |
2 | 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 |
|
5506 | 7 |
* published by the Free Software Foundation. Oracle designates this |
2 | 8 |
* particular file as subject to the "Classpath" exception as provided |
5506 | 9 |
* by Oracle in the LICENSE file that accompanied this code. |
2 | 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 |
* |
|
5506 | 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. |
|
2 | 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 |
||
10110 | 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? |
|
2 | 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) { |
|
10110 | 76 |
List<String> as = Arrays.asList(args); |
77 |
for (Iterator<String> i = as.iterator(); i.hasNext();) { |
|
78 |
String a = i.next(); |
|
2 | 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(); |
|
10110 | 88 |
maxDepth = Integer.parseInt(i.next()); |
2 | 89 |
} else if (a.equals("-mb")) { |
90 |
if (!i.hasNext()) |
|
91 |
usage(); |
|
10110 | 92 |
maxBits = Integer.parseInt(i.next()); |
2 | 93 |
} else if (a.equals("-t")) { |
94 |
if (!i.hasNext()) |
|
95 |
usage(); |
|
10110 | 96 |
vtype = i.next(); |
2 | 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++) { |
|
10110 | 153 |
String w = keys.get(i); |
154 |
String v = values.get(i); |
|
2 | 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(); |
|
22639
37f4508257fe
8033236: Update GensrcCharsetMapping.gmk to build-infra standards
ihse
parents:
21805
diff
changeset
|
184 |
if (verbose) { |
37f4508257fe
8033236: Update GensrcCharsetMapping.gmk to build-infra standards
ihse
parents:
21805
diff
changeset
|
185 |
if (cln != null) |
37f4508257fe
8033236: Update GensrcCharsetMapping.gmk to build-infra standards
ihse
parents:
21805
diff
changeset
|
186 |
err.print(cln + ": "); |
37f4508257fe
8033236: Update GensrcCharsetMapping.gmk to build-infra standards
ihse
parents:
21805
diff
changeset
|
187 |
err.println("Table size " + (1 << nb) + " (" + nb + " bits)" |
37f4508257fe
8033236: Update GensrcCharsetMapping.gmk to build-infra standards
ihse
parents:
21805
diff
changeset
|
188 |
+ ", shift " + shift |
37f4508257fe
8033236: Update GensrcCharsetMapping.gmk to build-infra standards
ihse
parents:
21805
diff
changeset
|
189 |
+ ", max chain depth " + md); |
37f4508257fe
8033236: Update GensrcCharsetMapping.gmk to build-infra standards
ihse
parents:
21805
diff
changeset
|
190 |
} |
2 | 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++) { |
|
10110 | 219 |
String w = keys.get(i); |
2 | 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 |
} |