001: /*
002: *
003: *
004: * Copyright 1990-2007 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 jcc;
028:
029: import components.UnicodeConstant;
030: import components.StringConstant;
031: import util.Localizer;
032:
033: /*
034: * This class duplicates the String to ID hashing that Java
035: * does internally. An initial set of hash tables is produced
036: * that the Java runtime will use.
037: * (perhaps this really belongs in package vm?)
038: */
039:
040: public class Str2ID {
041: // The contents of each hash table chain
042: public int hashTableSize;
043: public int used = 0;
044: public int baseId = 1;
045: public Str2ID next = null;
046: public UnicodeConstant strings[];
047: public StringConstant parameters[] = null;
048: public int hashbits[];
049:
050: boolean locked = false; // check that nothing new is added.
051:
052: public static final int DEFAULT_hashTableSize = 2003;
053:
054: public Str2ID() {
055: this (DEFAULT_hashTableSize, true);
056: }
057:
058: public Str2ID(int size) {
059: this (size, false);
060: }
061:
062: private Str2ID(int size, boolean knownPrime) {
063: if (!knownPrime) {
064: size |= 1;
065: while (!isPrime(size))
066: size += 2;
067: }
068: hashTableSize = size;
069: strings = new UnicodeConstant[size];
070: hashbits = new int[size];
071: overflowPoint = (int) (hashTableSize * 0.8);
072: }
073:
074: // Use values in java/util/util.c
075:
076: int overflowPoint;
077: public static Str2ID sigHash = new Str2ID();
078:
079: // Treat val as an unsigned quantity and do the MOD operation
080: int unsignedMod(int val) {
081: if (val >= 0) {
082: return val % hashTableSize;
083: } else {
084: return (int) (((long) val & 0xffffffffL) % (long) hashTableSize);
085: }
086: }
087:
088: static int hashString(String str) {
089: int result = 0;
090: for (int i = 0; i < str.length(); i++) {
091: result = result * 37 + (int) str.charAt(i);
092: }
093:
094: return result;
095: }
096:
097: public int getID(UnicodeConstant str, StringConstant parameter) {
098: Str2ID head = this ;
099: int index;
100: int hash = hashString(str.string);
101: int phash = hash & 0x7fffffff;
102: int secondaryHash = (hash & 7) + 1;
103:
104: Str2ID chain = head;
105: for (;;) {
106: index = chain.unsignedMod(hash);
107: while (chain.strings[index] != null) {
108: if ((chain.hashbits[index] == phash)
109: && chain.strings[index].string
110: .equals(str.string)) {
111: // We found the string, calculate the ID
112: return chain.baseId + index;
113: }
114: index -= secondaryHash;
115: if (index < 0) {
116: index += chain.hashTableSize;
117: }
118: }
119:
120: // Didn't find the string in this chain. . . .
121: if (chain.next == null) {
122: break;
123: } else {
124: chain = chain.next;
125: }
126: }
127:
128: if (locked) {
129: throw new NullPointerException(Localizer.getString(
130: "str2id.attempting_to_add_to_table_when_locked",
131: str));
132:
133: }
134: if (chain.used >= chain.overflowPoint) {
135: chain.next = new Str2ID();
136: chain.next.baseId = chain.baseId + chain.hashTableSize;
137: chain = chain.next;
138: index = chain.unsignedMod(hash);
139: }
140:
141: chain.strings[index] = str;
142: chain.hashbits[index] = phash;
143: if (parameter != null) {
144: if (chain.parameters == null) {
145: chain.parameters = new StringConstant[chain.hashTableSize];
146: }
147: chain.parameters[index] = parameter;
148: }
149: chain.used++;
150: return chain.baseId + index;
151: }
152:
153: public int getID(String str) {
154: return getID(new UnicodeConstant(str), (StringConstant) null);
155: }
156:
157: public int getID(UnicodeConstant name, UnicodeConstant sig) {
158: return (getID(name, (StringConstant) null) << 16)
159: + getID(sig, (StringConstant) null);
160: }
161:
162: public int getID(String name, String sig) {
163: return (getID(name) << 16) + getID(sig);
164: }
165:
166: public void setLocked(boolean lock) {
167: this .locked = lock;
168: }
169:
170: public Str2ID rehash() {
171: Str2ID newchain, chain;
172: int count = 0;
173: for (chain = this ; chain != null; chain = chain.next) {
174: count += chain.used;
175: }
176: newchain = new Str2ID((int) Math.ceil(1.25 * count));
177:
178: for (chain = this ; chain != null; chain = chain.next) {
179: UnicodeConstant strings[] = chain.strings;
180: StringConstant parameters[] = chain.parameters;
181: for (int i = chain.hashTableSize; --i >= 0;) {
182: UnicodeConstant string = strings[i];
183: if (string != null)
184: newchain.getID(string, parameters == null ? null
185: : parameters[i]);
186: }
187: }
188: return newchain;
189: }
190:
191: static boolean isPrime(int n) {
192: if ((n % 2) == 0)
193: return false;
194: int sqrt = (int) Math.sqrt(n);
195: for (int i = 3; i <= sqrt; i += 2) {
196: if ((n % i) == 0)
197: return false;
198: }
199: return true;
200: }
201: }
|