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