make/tools/src/build/tools/hasher/Hasher.java - toolchain/jdk/jdk9_jdk - Git at Google

 /*
  * Copyright (c) 2004, 2005, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
  * under the terms of the GNU General Public License version 2 only, as
  * published by the Free Software Foundation.  Oracle designates this
  * particular file as subject to the "Classpath" exception as provided
  * by Oracle in the LICENSE file that accompanied this code.
  *
  * This code is distributed in the hope that it will be useful, but WITHOUT
  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  * version 2 for more details (a copy is included in the LICENSE file that
  * accompanied this code).
  *
  * You should have received a copy of the GNU General Public License version
  * 2 along with this work; if not, write to the Free Software Foundation,
  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  *
  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  * or visit www.oracle.com if you need additional information or have any
  * questions.
  */

 package build.tools.hasher;

 import java.io.*;
 import java.util.*;


 /**
  * Reads a map in the form of a sequence of key/value-expression pairs from the
  * standard input, attempts to construct a hash map that fits within the given
  * table-size and chain-depth constraints, and, if successful, writes source
  * code to the standard output for a subclass of sun.util.PreHashedMap that
  * implements the map.
  *
  * @see sun.util.PreHashedMap
  *
  * @author Mark Reinhold
  */

 public class Hasher {

     // This class cannot, sadly, make use of 1.5 features since it must be
     // compiled and run with the bootstrap JDK, which is 1.4.2.

     static final PrintStream out = System.out;
     static final PrintStream err = System.err;

     boolean verbose = false;

     List keys = new ArrayList();        // Key strings
     List values = new ArrayList();      // Value expressions
     String pkg = null;                  // Package prefix for generated class
     String cln = null;                  // Name of generated class
     String vtype = "String";            // Value type
     int maxBits = 11;                   // lg table size
     int maxDepth = 3;                   // Max chain depth
     boolean inner = false;              // Generating an inner class?
     boolean empty = false;              // Generating an empty table?

     void usage() {
         err.println("usage: java Hasher [options] [[pkgName.]ClassName]");
         err.println("options:");
         err.println("    -e           generate empty table (ignores value exprs)");
         err.println("    -i           generate a static inner class");
         err.println("    -md depth    max chain depth (default 3)");
         err.println("    -mb bits     max index bits (lg of table size, default 10)");
         err.println("    -t type      value type (default String)");
         err.println("    -v           verbose");
         err.println("Key/value-expression pairs are read from standard input");
         err.println("If class name is given then source is written to standard output");
         System.exit(1);
     }

     Hasher(String[] args) {
         List as = Arrays.asList(args);
         for (Iterator i = as.iterator(); i.hasNext();) {
             String a = (String)i.next();
             if (a.equals("-e")) {
                 empty = true;
             } else if (a.equals("-i")) {
                 inner = true;
             } else if (a.equals("-v")) {
                 verbose = true;
             } else if (a.equals("-md")) {
                 if (!i.hasNext())
                     usage();
                 maxDepth = Integer.parseInt((String)i.next());
             } else if (a.equals("-mb")) {
                 if (!i.hasNext())
                     usage();
                 maxBits = Integer.parseInt((String)i.next());
             } else if (a.equals("-t")) {
                 if (!i.hasNext())
                     usage();
                 vtype = (String)i.next();
             } else if (a.startsWith("-")) {
                 usage();
             } else {
                 int j = a.lastIndexOf('.');
                 if (j >= 0) {
                     pkg = a.substring(0, j);
                     cln = a.substring(j + 1);
                 } else {
                     cln = a;
                 }
             }
         }
         if (verbose)
             err.println("pkg=" + pkg + ", cln=" + cln);
     }

     // Read keys and values
     //
     Hasher load() throws IOException {
         BufferedReader br
             = new BufferedReader(new InputStreamReader(System.in));
         for (String ln; (ln = br.readLine()) != null;) {
             String[] ws = ln.split(",?\\s+", 2);
             String w = ws[0].replaceAll("\"", "");
             if (keys.contains(w))
                 throw new RuntimeException("Duplicate word in input: " + w);
             keys.add(w);
             if (ws.length < 2)
                 throw new RuntimeException("Missing expression for key " + w);
             values.add(ws[1]);
         }
         return this;
     }

     Object[] ht;                        // Hash table itself
     int nb;                             // Number of bits (lg table size)
     int md;                             // Maximum chain depth
     int mask;                           // Hash-code mask
     int shift;                          // Hash-code shift size

     int hash(String w) {
         return (w.hashCode() >> shift) & mask;
     }

     // Build a hash table of size 2^nb, shifting the hash code by s bits
     //
     void build(int nb, int s) {

         this.nb = nb;
         this.shift = s;
         int n = 1 << nb;
         this.mask = n - 1;
         ht = new Object[n];
         int nw = keys.size();

         for (int i = 0; i < nw; i++) {
             String w = (String)keys.get(i);
             String v = (String)values.get(i);
             int h = hash(w);
             if (ht[h] == null)
                 ht[h] = new Object[] { w, v };
             else
                 ht[h] = new Object[] { w, v, ht[h] };
         }

         this.md = 0;
         for (int i = 0; i < n; i++) {
             int d = 1;
             for (Object[] a = (Object[])ht[i];
                  a != null && a.length > 2;
                  a = (Object[])a[2], d++);
             this.md = Math.max(md, d);
         }

     }

     Hasher build() {
         // Iterate through acceptable table sizes
         for (int nb = 2; nb < maxBits; nb++) {
             // Iterate through possible shift sizes
             for (int s = 0; s < (32 - nb); s++) {
                 build(nb, s);
                 if (verbose)
                     err.println("nb=" + nb + " s=" + s + " md=" + md);
                 if (md <= maxDepth) {
                     // Success
                     out.flush();
                     if (cln != null)
                         err.print(cln + ": ");
                     err.println("Table size " + (1 << nb) + " (" + nb + " bits)"
                                 + ", shift " + shift
                                 + ", max chain depth " + md);
                     return this;
                 }
             }
         }
         throw new RuntimeException("Cannot find a suitable size"
                                    + " within given constraints");
     }

     // Look for the given key in the hash table
     //
     String get(String k) {
         int h = hash(k);
         Object[] a = (Object[])ht[h];
         for (;;) {
             if (a[0].equals(k))
                 return (String)a[1];
             if (a.length < 3)
                 return null;
             a = (Object[])a[2];
         }
     }

     // Test that all input keys can be found in the table
     //
     Hasher test() {
         if (verbose)
             err.println();
         for (int i = 0, n = keys.size(); i < n; i++) {
             String w = (String)keys.get(i);
             String v = get(w);
             if (verbose)
                 err.println(hash(w) + "\t" + w);
             if (!v.equals(values.get(i)))
                 throw new Error("Incorrect value: " + w + " --> "
                                 + v + ", should be " + values.get(i));
         }
         return this;
     }

     String ind = "";                    // Indent prefix

     // Generate code for a single table entry
     //
     void genEntry(Object[] a, int depth, PrintWriter pw) {
         Object v = empty ? null : a[1];
         pw.print("new Object[] { \"" + a[0] + "\", " + v);
         if (a.length < 3) {
             pw.print(" }");
             return;
         }
         pw.println(",");
         pw.print(ind + "                     ");
         for (int i = 0; i < depth; i++)
             pw.print("    ");
         genEntry((Object[])a[2], depth + 1, pw);
         pw.print(" }");
     }

     // Generate a PreHashedMap subclass from the computed hash table
     //
     Hasher generate() throws IOException {
         if (cln == null)
             return this;
         PrintWriter pw
             = new PrintWriter(new BufferedWriter(new OutputStreamWriter(out)));

         if (inner)
             ind = "    ";

         if (!inner && pkg != null) {
             pw.println();
             pw.println("package " + pkg + ";");
             pw.println();
         }

         if (inner) {
             pw.println(ind + "private static final class " + cln);
         } else {
             pw.println();
             pw.println("public final class " + cln);
         }
         pw.println(ind + "    extends sun.util.PreHashedMap<" + vtype +">");
         pw.println(ind + "{");

         pw.println();
         pw.println(ind + "    private static final int ROWS = "
                    + ht.length + ";");
         pw.println(ind + "    private static final int SIZE = "
                    + keys.size() + ";");
         pw.println(ind + "    private static final int SHIFT = "
                    + shift + ";");
         pw.println(ind + "    private static final int MASK = 0x"
                    + Integer.toHexString(mask) + ";");
         pw.println();

         pw.println(ind + "    " + (inner ? "private " : "public ")
                    + cln + "() {");
         pw.println(ind + "        super(ROWS, SIZE, SHIFT, MASK);");
         pw.println(ind + "    }");
         pw.println();

         pw.println(ind + "    protected void init(Object[] ht) {");
         for (int i = 0; i < ht.length; i++) {
             if (ht[i] == null)
                 continue;
             Object[] a = (Object[])ht[i];
             pw.print(ind + "        ht[" + i + "] = ");
             genEntry(a, 0, pw);
             pw.println(";");
         }
         pw.println(ind + "    }");
         pw.println();

         pw.println(ind + "}");
         if (inner)
             pw.println();

         pw.close();
         return this;
     }

     public static void main(String[] args) throws IOException {
         new Hasher(args)
             .load()
             .build()
             .test()
             .generate();
     }

 }
	/*
	* Copyright (c) 2004, 2005, Oracle and/or its affiliates. All rights reserved.
	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	*
	* This code is free software; you can redistribute it and/or modify it
	* under the terms of the GNU General Public License version 2 only, as
	* published by the Free Software Foundation. Oracle designates this
	* particular file as subject to the "Classpath" exception as provided
	* by Oracle in the LICENSE file that accompanied this code.
	*
	* This code is distributed in the hope that it will be useful, but WITHOUT
	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	* version 2 for more details (a copy is included in the LICENSE file that
	* accompanied this code).
	*
	* You should have received a copy of the GNU General Public License version
	* 2 along with this work; if not, write to the Free Software Foundation,
	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
	* or visit www.oracle.com if you need additional information or have any
	* questions.
	*/

	package build.tools.hasher;

	import java.io.*;
	import java.util.*;


	/**
	* Reads a map in the form of a sequence of key/value-expression pairs from the
	* standard input, attempts to construct a hash map that fits within the given
	* table-size and chain-depth constraints, and, if successful, writes source
	* code to the standard output for a subclass of sun.util.PreHashedMap that
	* implements the map.
	*
	* @see sun.util.PreHashedMap
	*
	* @author Mark Reinhold
	*/

	public class Hasher {

	// This class cannot, sadly, make use of 1.5 features since it must be
	// compiled and run with the bootstrap JDK, which is 1.4.2.

	static final PrintStream out = System.out;
	static final PrintStream err = System.err;

	boolean verbose = false;

	List keys = new ArrayList(); // Key strings
	List values = new ArrayList(); // Value expressions
	String pkg = null; // Package prefix for generated class
	String cln = null; // Name of generated class
	String vtype = "String"; // Value type
	int maxBits = 11; // lg table size
	int maxDepth = 3; // Max chain depth
	boolean inner = false; // Generating an inner class?
	boolean empty = false; // Generating an empty table?

	void usage() {
	err.println("usage: java Hasher [options] [[pkgName.]ClassName]");
	err.println("options:");
	err.println(" -e generate empty table (ignores value exprs)");
	err.println(" -i generate a static inner class");
	err.println(" -md depth max chain depth (default 3)");
	err.println(" -mb bits max index bits (lg of table size, default 10)");
	err.println(" -t type value type (default String)");
	err.println(" -v verbose");
	err.println("Key/value-expression pairs are read from standard input");
	err.println("If class name is given then source is written to standard output");
	System.exit(1);
	}

	Hasher(String[] args) {
	List as = Arrays.asList(args);
	for (Iterator i = as.iterator(); i.hasNext();) {
	String a = (String)i.next();
	if (a.equals("-e")) {
	empty = true;
	} else if (a.equals("-i")) {
	inner = true;
	} else if (a.equals("-v")) {
	verbose = true;
	} else if (a.equals("-md")) {
	if (!i.hasNext())
	usage();
	maxDepth = Integer.parseInt((String)i.next());
	} else if (a.equals("-mb")) {
	if (!i.hasNext())
	usage();
	maxBits = Integer.parseInt((String)i.next());
	} else if (a.equals("-t")) {
	if (!i.hasNext())
	usage();
	vtype = (String)i.next();
	} else if (a.startsWith("-")) {
	usage();
	} else {
	int j = a.lastIndexOf('.');
	if (j >= 0) {
	pkg = a.substring(0, j);
	cln = a.substring(j + 1);
	} else {
	cln = a;
	}
	}
	}
	if (verbose)
	err.println("pkg=" + pkg + ", cln=" + cln);
	}

	// Read keys and values
	//
	Hasher load() throws IOException {
	BufferedReader br
	= new BufferedReader(new InputStreamReader(System.in));
	for (String ln; (ln = br.readLine()) != null;) {
	String[] ws = ln.split(",?\\s+", 2);
	String w = ws[0].replaceAll("\"", "");
	if (keys.contains(w))
	throw new RuntimeException("Duplicate word in input: " + w);
	keys.add(w);
	if (ws.length < 2)
	throw new RuntimeException("Missing expression for key " + w);
	values.add(ws[1]);
	}
	return this;
	}

	Object[] ht; // Hash table itself
	int nb; // Number of bits (lg table size)
	int md; // Maximum chain depth
	int mask; // Hash-code mask
	int shift; // Hash-code shift size

	int hash(String w) {
	return (w.hashCode() >> shift) & mask;
	}

	// Build a hash table of size 2^nb, shifting the hash code by s bits
	//
	void build(int nb, int s) {

	this.nb = nb;
	this.shift = s;
	int n = 1 << nb;
	this.mask = n - 1;
	ht = new Object[n];
	int nw = keys.size();

	for (int i = 0; i < nw; i++) {
	String w = (String)keys.get(i);
	String v = (String)values.get(i);
	int h = hash(w);
	if (ht[h] == null)
	ht[h] = new Object[] { w, v };
	else
	ht[h] = new Object[] { w, v, ht[h] };
	}

	this.md = 0;
	for (int i = 0; i < n; i++) {
	int d = 1;
	for (Object[] a = (Object[])ht[i];
	a != null && a.length > 2;
	a = (Object[])a[2], d++);
	this.md = Math.max(md, d);
	}

	}

	Hasher build() {
	// Iterate through acceptable table sizes
	for (int nb = 2; nb < maxBits; nb++) {
	// Iterate through possible shift sizes
	for (int s = 0; s < (32 - nb); s++) {
	build(nb, s);
	if (verbose)
	err.println("nb=" + nb + " s=" + s + " md=" + md);
	if (md <= maxDepth) {
	// Success
	out.flush();
	if (cln != null)
	err.print(cln + ": ");
	err.println("Table size " + (1 << nb) + " (" + nb + " bits)"
	+ ", shift " + shift
	+ ", max chain depth " + md);
	return this;
	}
	}
	}
	throw new RuntimeException("Cannot find a suitable size"
	+ " within given constraints");
	}

	// Look for the given key in the hash table
	//
	String get(String k) {
	int h = hash(k);
	Object[] a = (Object[])ht[h];
	for (;;) {
	if (a[0].equals(k))
	return (String)a[1];
	if (a.length < 3)
	return null;
	a = (Object[])a[2];
	}
	}

	// Test that all input keys can be found in the table
	//
	Hasher test() {
	if (verbose)
	err.println();
	for (int i = 0, n = keys.size(); i < n; i++) {
	String w = (String)keys.get(i);
	String v = get(w);
	if (verbose)
	err.println(hash(w) + "\t" + w);
	if (!v.equals(values.get(i)))
	throw new Error("Incorrect value: " + w + " --> "
	+ v + ", should be " + values.get(i));
	}
	return this;
	}

	String ind = ""; // Indent prefix

	// Generate code for a single table entry
	//
	void genEntry(Object[] a, int depth, PrintWriter pw) {
	Object v = empty ? null : a[1];
	pw.print("new Object[] { \"" + a[0] + "\", " + v);
	if (a.length < 3) {
	pw.print(" }");
	return;
	}
	pw.println(",");
	pw.print(ind + " ");
	for (int i = 0; i < depth; i++)
	pw.print(" ");
	genEntry((Object[])a[2], depth + 1, pw);
	pw.print(" }");
	}

	// Generate a PreHashedMap subclass from the computed hash table
	//
	Hasher generate() throws IOException {
	if (cln == null)
	return this;
	PrintWriter pw
	= new PrintWriter(new BufferedWriter(new OutputStreamWriter(out)));

	if (inner)
	ind = " ";

	if (!inner && pkg != null) {
	pw.println();
	pw.println("package " + pkg + ";");
	pw.println();
	}

	if (inner) {
	pw.println(ind + "private static final class " + cln);
	} else {
	pw.println();
	pw.println("public final class " + cln);
	}
	pw.println(ind + " extends sun.util.PreHashedMap<" + vtype +">");
	pw.println(ind + "{");

	pw.println();
	pw.println(ind + " private static final int ROWS = "
	+ ht.length + ";");
	pw.println(ind + " private static final int SIZE = "
	+ keys.size() + ";");
	pw.println(ind + " private static final int SHIFT = "
	+ shift + ";");
	pw.println(ind + " private static final int MASK = 0x"
	+ Integer.toHexString(mask) + ";");
	pw.println();

	pw.println(ind + " " + (inner ? "private " : "public ")
	+ cln + "() {");
	pw.println(ind + " super(ROWS, SIZE, SHIFT, MASK);");
	pw.println(ind + " }");
	pw.println();

	pw.println(ind + " protected void init(Object[] ht) {");
	for (int i = 0; i < ht.length; i++) {
	if (ht[i] == null)
	continue;
	Object[] a = (Object[])ht[i];
	pw.print(ind + " ht[" + i + "] = ");
	genEntry(a, 0, pw);
	pw.println(";");
	}
	pw.println(ind + " }");
	pw.println();

	pw.println(ind + "}");
	if (inner)
	pw.println();

	pw.close();
	return this;
	}

	public static void main(String[] args) throws IOException {
	new Hasher(args)
	.load()
	.build()
	.test()
	.generate();
	}

	}