001: /*
002: * @(#)AsciiTable.java 1.12 06/10/10
003: *
004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License version
009: * 2 only, as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful, but
012: * WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * General Public License version 2 for more details (a copy is
015: * included at /legal/license.txt).
016: *
017: * You should have received a copy of the GNU General Public License
018: * version 2 along with this work; if not, write to the Free Software
019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
020: * 02110-1301 USA
021: *
022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
023: * Clara, CA 95054 or visit www.sun.com if you need additional
024: * information or have any questions.
025: *
026: */
027: package vm;
028:
029: import components.*;
030: import java.util.Hashtable;
031: import java.util.Vector;
032: import Util;
033:
034: /*
035: * There are two string-like data types in today's JDK:
036: * 1) zero-terminated, C-language, ASCII strings
037: * 2) Java Strings.
038: *
039: * The former arise from:
040: * (a) UTF encoding of Java class, method, field names and type
041: * signatures, used for linkage
042: * (b) UTF encoded forms of Java String constants, used as keys
043: * for the intern-ing of said constants.
044: *
045: * This class takes a collection of ASCII strings (collected using addString)
046: * and finds those strings which are suffixes of other, longer strings in
047: * the collection. This allows some sharing of data when we produce a list
048: * of zero-terminated ASCII ( i.e. asciz ) strings as part of the runtime
049: * data.
050: *
051: * For example, the string "a" can be represented as a pointer to the end
052: * of the string "ba".
053: */
054:
055: public class AsciiTable {
056: PostFixTreeElement tree = null;
057: Hashtable stringHash = new Hashtable();
058: Vector table = null;
059:
060: // Add a string to the list
061: public void addString(UnicodeConstant str) {
062: if (str.UTFstring == null) {
063: str.UTFstring = Util.unicodeToUTF(str.string);
064: }
065: PostFixTreeElement elem = new PostFixTreeElement(str);
066: tree = PostFixTreeElement.insert(tree, elem);
067: stringHash.put(str.string, str);
068: }
069:
070: public UnicodeConstant getConstant(String key) {
071: return (UnicodeConstant) stringHash.get(key);
072: }
073:
074: // Go through all of the strings that have been added and find
075: // those that can be stored as a pointer to a postfix.
076: public void computeAsciiTable() {
077: table = tree.produceTable();
078: }
079:
080: // Get the whole table, as for printing.
081: public Vector getTable() {
082: return table;
083: }
084:
085: // Ordering function for tree. The comparison is done using
086: // the end of the strings, working backwards.
087: static public boolean lessThan(UnicodeConstant aConst,
088: UnicodeConstant bConst) {
089: String a = aConst.UTFstring;
090: String b = bConst.UTFstring;
091: int aLen = a.length();
092: int bLen = b.length();
093:
094: for (int i = 1; i <= aLen && i <= bLen; i++) {
095: if (a.charAt(aLen - i) < b.charAt(bLen - i)) {
096: return true;
097: } else if (a.charAt(aLen - i) > b.charAt(bLen - i)) {
098: return false;
099: }
100: }
101:
102: return aLen <= bLen;
103: }
104: }
105:
106: class PostFixTreeElement {
107: private UnicodeConstant str;
108: private PostFixTreeElement left = null, right = null;
109:
110: //public int tindex = -1;
111:
112: public PostFixTreeElement(UnicodeConstant a) {
113: str = a;
114: }
115:
116: static public PostFixTreeElement insert(PostFixTreeElement t,
117: PostFixTreeElement elem) {
118: if (t == null) {
119: return elem;
120: } else if (AsciiTable.lessThan(elem.str, t.str)) {
121: t.left = insert(t.left, elem);
122: } else {
123: t.right = insert(t.right, elem);
124: }
125: return t;
126: }
127:
128: public Vector produceTable() {
129: Vector t = new Vector();
130: PostFixTreeElement last = produceTable(null, t);
131: return t;
132: }
133:
134: // This function assigns an index to each of the AsciiConstant strings,
135: // while printing out the tree.
136: //
137: // In the following, we talk about "r-alphabetic" ordering. This is
138: // alphabetic lexicogrphic sorting, but starting from the end of the string.
139: // Our tree is a binary tree in which everything in the left node is
140: // r-alphabetically less than the root, and everything in the right node
141: // is r-alphabetically greater than the root.
142: //
143: // The following code makes use of the fact that if a string is a suffix of
144: // any other string in the list, then it is certainly of suffc of the next
145: // string r-alphabetically.
146: //
147: // So we just go through the tree in reverse r-alphabetic order. As we
148: // look at each item, the variable "last" contains the next greater string
149: // r-alphabetically. Either the current string is a suffix of "last", or
150: // else it can't be a suffix of any string whatsoever in the tree.
151: //
152: // The return value is the left-most node (i.e. smallest ralphabetically)
153: // of the subtree.
154: private PostFixTreeElement produceTable(PostFixTreeElement last,
155: Vector t) {
156: // Look at the items on the right subtree.
157: if (right != null) {
158: last = right.produceTable(last, t);
159: }
160: int index = 0;
161: if (last != null) {
162: // assume not a suffix
163: index = last.str.stringTableOffset
164: + last.str.UTFstring.length() + 1;
165: if (last.str.UTFstring.endsWith(this .str.UTFstring)) {
166: index -= (this .str.UTFstring.length() + 1);
167: this .str.isSuffix = true;
168: }
169: }
170: t.addElement(this.str);
171: if (!this.str.isSuffix) {
172: last = this;
173: }
174: this.str.stringTableOffset = index;
175: if (left != null) {
176: last = left.produceTable(last, t);
177: }
178: return last;
179: }
180: }
|