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.charsetmapping; 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 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 hash(String w)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 // build(int nb, int s)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 build()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 // get(String k)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 // test()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 // genEntry(Object[] a, int depth, PrintStream out)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 // generate(PrintStream out)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 Hasher(List<String> keys, List<String> values, String pkg, String cln, String vtype, int maxBits, int maxDepth, boolean inner, boolean empty, boolean verbose)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 genClass(PrintStream out, List<String> keys, List<String> values, String pkg, String cln, String vtype, int maxBits, int maxDepth, boolean inner, boolean empty, boolean verbose)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